texts: How to generate a grammer from this language?

texts:
I'm trying to generate a grammar from this language:

L={a^i b^j c^k d^l :  i+j=k+l}

to be clear its a in the power of i and b in the power of j... and so on, so that i+j will equal k+l,
I would love an explanation how to get to the solution as well, thank you!


texts: Segmented address / normal virtual address

texts: In a cpu with segmented memory, can an address only be accessed with a segmented address, or can a normal virtual address also be used?


texts: Information theory from a (very pure) mathematician's perspective

texts:
I'm a pure mathematician interested in learning about information theory. Unfortunately, I'm about as pure as they come - my specialty is mathematical logic, and I have absolutely no experience with programming or anything of a computational nature. I tried looking at Shannon's original paper, but the profusion of numbers intimidated me (I'm a mathematician after all!) When he starts discussing the particulars of coding specific alphabets, my brain begins to asking whether this attention to detail is really necessary and soon zones out... It took Church's thesis for granted some time ago. (Pathetic, I know.)

I'm wondering if there's some introduction to information theory written with people like me in mind. Something which uses the language of measure theory and recursion theory, and works in the greatest generality. Perhaps an expert in the area has written some notes in this direction as an idle folly?

I realize that this might not be the place to ask this question, and apologize if this is the case.


texts: Finding a graph where the edge set satisfies a set of integer equations

texts:
There is an easy and hard version of the problem I am asking about, so I will start with the easy to make for clearer reading.

Suppose that we are have a set of vertices $V =\{v_1,v_2,...,v_n\}$ and sets $S_1,S_2,...,S_m \subset V \times V$. Let

$s_{ijk} = 1$ if $\ (v_j,v_k) \in S_i $, 0 otherwise.

Given integers $\ k_1,...,k_m$ we want to find whether the set of equations

$$\begin{align*}
k_1 &= \sum_{j,k} a_{jk} s_{1jk}\\
k_2 &= \sum_{j,k} a_{jk} s_{2jk}\\
 &\vdots\\
k_m &= \sum_{j,k} a_{jk} s_{mjk}
\end{align*}$$

has a solution with all of the $a_{11}, a_{12}, ... , a_{nn}$ indices in $\{0,1\}$.

Explanation

This set of 0-1 equations is equivalent to checking whether or not there exists a (simple directed) graph with $\ k_i$ edges from each of the subsets $\ S_i$. My immediate instinct is that this problem is solvable in polynomial time, say by a straightforward backtracking algorithm. Another possibility is to solve the system using the appropriate technique (say Hermite Normal Form) and then applying LLL to get a short basis for the solutions. The proof that this is solvable in polynomial time isn't entirely clear to me though.

Example

We are given $\ v_1, v_2, v_3.$

$\ S_1 = (v_2, v_3) $

$\ S_2 = (v_1, v_3), (v_2, v_3)$

$\ k_1 = 1, k_2 = 0$

We return false because we have to pick $\ (v_2,v_3)$ but this forces $\ k_2 > 0$ since we have to pick it in the second set as well.

The harder version:

Does there exist a (directed) graph $G$ with $\ k_i $ edges from each subset $\ S_i$ such that

$\ G = cl(G)$,

where $\ cl(G) $ denotes the transitive closure?

We can solve this by testing the feasibility of a set of 0-1 linear equations and inequalities, but as we should know that problem is NP hard in general (unlike solving linear integer equations). However it does not look at all trivial to show that this particular problem is NP hard.

Questions

Can the first problem always be solved in polynomial time?

Is the second problem NP hard?


texts: Computing the closest point inside an intersection of half-spaces

texts:
Is there an efficient way to compute, given a point, the closest point to it that's on the inside of an intersection of half-spaces?

For example, given the half-spaces a & b, the closest point to p that's "inside" the half-spaces is x. + denotes which side is "inside" the half-spaces a and b.

.p
       ^
       |
       |
       | x
   <---.--------------> b
       |       +
       |
       | +
       |
       v a

I'm particularly interested in an algorithm for half-spaces in 3D (planes)

My current line of thinking leads me to have to compute intersections of each half space, and then find the shortest point by picking from the shortest distance to each half-space and each intersection (line, point) that's within all the half-spaces. Is there a better way?


texts: Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given?

texts:
I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their:

Case 1. Preorder & inorder traversals are given or

Case 2. postorder & inorder traversals are given

We can not determine the tree if only one of the traversals are given because there will be finitely many trees possible.

My question is that, is there a way to calculate the number of trees possible?


texts: Why do i have to show that a problem L $ \in $ NP before i start a polynomial reduction?

texts:
i want to do a polynomial reduction from the Independent-Set-Problem which is NP-complete to the AUCTION-Problem, to show that AUCTION $\in$ NP-complete,
but why do i always have to show first, that our problem(in this case AUCTION) $ \in $ NP?


texts: Is the union of computable enumerable sets computably enumerable

texts:
Let $\{A_n : n \in \mathbb{N}\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup_n A_n$ c.e.?
That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be true?


texts: Ordering of conditions in multi-way conditional constructs

texts: Most programming languages provide multi-way conditional constructs (like cond in Lisp, guards in Haskell, etc) that allow one to define program behavior according to different conditions.  But most of them also implies a default top-down ordering: the next condition is checked only when all preceding conditions are unsatisfied.  I wonder if there is any work on conditional constructs that does not follow this convention but rather automatically sort the conditions according to some order.  I can foresee how hard it is to get conditions independent.  Maybe it is not feasible anyway?


texts: Linear time multiplication on RAM machine?

texts:
This page says following:

  Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM

Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) using RAM?


texts: How to show that any computable function is bounded above by Busy Beaver Function?

texts:
Despite the endless hours of googling, pretty much all of them used an alternative definition of Busy Beaver function. The definition BB(k) I'm interested in is the maximum number of 1's that can be written by k-state before it halts, but the other definition they used was the maximum number of steps, and they're not equivalent.

And one of the techniques they used is by reduction from halting problem, that if there was any computable function f(x) bounding above the function BB(k), you can solve halting problem in a finite amount of time using the alternative definition, but this argument doesn't work for the definition of BB(k) I am interested in. How do we show that BB(k) is asymptotically larger than any computable function f(x)?


texts:
Need to prove $(a + ab)^*a = a(a + ba)^*$ by using regular algebra.
Concatenation does not commute. So repeated use of commutativity will fail. I am getting confused about which identity I should use to prove this. What I can interpret is that I just need to change the side of $a$ but the $^*$ must be kept outside. But I am not able to do this.
Any help will be appreciated.


texts:
I came across this paper and attempting to go through the implementation of randomized selection algorithm on page 8.

Step 1 of the algorithm suggest to compute $s = PrefixSum(n_i, p)$. Where $p$ is the number of processes and $n_i$ starts simply as a number of elements in each process. Page 4 has a definition of parallel prefix, but I do not understand how to apply it in the algorithm.

Example, let $n_1 = 5, p = 2$, what is $PrefixSum(5,2)$?

Thank you.


texts: Does $\log(f(n)) = O(\log(g(n)))$ imply $f(n)=O(g(n))$?

texts:
Let $f(n) = O(g(n))$. Then we know that $\log(f(n)=O(\log(g(n)))$.

Is the converse of this statement also true?

Does $\log(f(n))=O(\log(g(n)))$ imply $f(n)=O(g(n))$?

Let's say $f(n)=n!\   g(n)=n^n$.

Since $n!=O(n^n)\rightarrow   \log n!=O(log n^n)$. This is true.

Now suppose I don't know that  $n!=O(n^n)$. But I know that $\log(n!)=\theta(n\log n)=\theta(\log n^n). $

Now since $\theta$ is symmetric I can conclude that $\log n^n=\theta \log(n!)$

$\log n^n=\theta (\log n!)$ means $\log n^n=O(\log n!)$.

If the converse that I am asking is true then $n^n=O(n!)$. But this is not true.

So this means the converse does not hold.

Am I true?


texts: How to build tree from graph with specific property

texts:
We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written.

We need to build tree such that for each node $i$, all nodes in the subtree of $i$ should be reachable from $i$ by going only through edges with values greater than $i$.

Such tree is always rooted at $0$ since all vertices can be reached from $0$.

For example, for the given graph:

(5, 1), (1, 2), (1, 3), (3, 4), (3, 0), (5, 2)
The tree we are looking for is rooted at 0 and its edges are:
(0, 1), (1, 2), (1, 3), (2, 5), (3, 4)

I have heard that this is solvable with using disjoint data set structure however I couldn't find a way how to properly find a way to connect the components.


texts: Complexity of factoring products of distinct prime numbers

texts:
Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$.

Do you know any results/references for the time complexity of this factoring problem?

Note: If the $p_{i_j}$'s are not assumed distinct, then the problem is just integer factorization. This is a very special case.


texts:
I've got the following problem:

I've got chessboard with fixed size N x M
I've got list of pieces, like 2 queens, 2 rooks (It can be any piece with exception of pawn).
I need to find every combination where none of the pieces is in a position to take any of the others

For example for chessboard 3 x 3 and 2 rooks and 1 king, possible solutions are:

 |R|        |R|      K| |      | |K
-+-+-      -+-+-     -+-+-    -+-+-
R| |        | |R      | |R    R| |
-+-+-      -+-+-     -+-+-    -+-+-
 | |K      K| |       |R|      |R|

What I came out with:

I create a whitelist of fields where the new piece can be placed (at the beginning it has all fields of the chessboard)
I take the first piece from the list
I place it on the first field I take from whitelist: (1,1)
I update whitelist excluding all fields that are threatened with this piece I placed
Here I branch out: I take next piece from the list and call my method recursively on every field from the whitelist (I also need to check, if placing new piece would threat already standing piece).
I repeat it until the last piece is placed
If there are pieces left, but no fields on whitelist I just finish that branch.

I noticed I can calculate results only for first quadrant (fields (1,1),(1,2)(2,1),(2,2) for my example. Rest of the solutions can be received by just mirroring results from the first quadrant.

Problem with my solution is, it's not very fast. For chessboard 7x7 and 7 pieces it takes ~15 minutes to finish. I implemented it with scala.

Do you have any tips about how can I improve it?


texts: Lower space bound on a turing machine accepting palindromes

texts:
Let
$$
PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace
$$
How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$?

I have a feeling that I need to use crossing sequences when crossing the middle of the input tape, but I'm not sure how to relate that to space.


texts: How to sort $N$ fractions from finite set

texts:
We have $10^5$ fractions: $\frac{p}{2^q}$ such that $0 \leq p,q \leq 10$.
  Find (fast) algorithm which sorts them.

I ask you to look at my proposition and tell me your ideas. $\frac{p}{q}$ is represented as the ordered pair $(p, q)$.

On input we have an array a.

My idea:

for i = 1 to n
do t[i] = a[i].first * 2^(10)
countsort (t)
bring results from t to a (remember about / 2^10)

II Idea:

for i = 1 to n do
   t[i] = a[i].first * 2^(10)
{ now we have only integer numbers }
sort t by counting (as bucket use bits)
for i = 1 to n do
   a[i] = t/2^10

In this way we have O(n + log (10 * 1024)n) = O(14n).
What about this solution ?


texts: Is every program is equivalent to a Push Down Automata?

texts: so I was reading about stack-organized computer. Does a stack-organized computer implies that every program is equivalent to (and not more powerful than) a  Push Down Automata?


texts: The meaning of ontology in computer science

texts:
I am reading a paper and ran into this word Ontology-based, What does it really mean? I did searching about it but still ambiguous to me, can someone elaborate this concept with an example?

Thank you


texts: Program interpretation for static analysis

texts:
Are there any implementations, or even academic work, regarding an application capable of looking at code and inferring what the code actually intends to do? For example, we give it a program that calculates the SQRT(x); it should go and annotate that particular piece of code with SQRT(X), regardless of implementation technique. Say you use recursion instead of a for loop; it should still be able to infer what the code intends to do. Pattern matching is not really an option here.

Another example: Say you have a program that computes the sum of inverse squares, starting at 0. It should print out the mathematical equivalent of that expression as result. Something like SIGMA 1/x^i


texts:
Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function:
$$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$
where $dist(x_1, x_2)$ is the number of edges in a path between two vertices/nodes $x_1$ and $x_2$.
What algorithm can I use?


texts: How to prove that justice isn't enough to produce all naturals?

texts:
I'm doing the exercises from the first chapter of the book "Temporal Verification of Reactive Systems Safety" by Manna and Pnueli.
However I find very difficult to solve the point c of problem 0.2.

At point a of problem 0.2 they introduce the program $ANY{-}NAT$. This program has the following propoerties:

All its computations terminate
For every $n \in \mathbb{N}$ there exist a computation that, when the program terminates, has $y = n$.

These properties are obtained by using parallel composition of processes (they ask to informally show these properties).

The point b asks to write a single process program that behaves like $ANY{-}NAT$. And I've done so, using the select operation to simulate interleaving and using compassion to exclude infinite runs from being valid computations.

In point c they ask to prove that no single-process program with only just transitions can have the semantics of $ANY{-}NAT$. The idea is that without compassion you cannot force termination and hence either the program only produce a finite number of outputs or it has a divergent computation.

But, how do I prove that? In particular, is there an elegant way to prove this?

What I was thinking was arguing that such a program must be of the form:

$$
\begin{array}{c}
I_0   \\
\textbf{while}~C_1~\textbf{do}~\ldots S_{1,1}~\textbf{or}~\cdots~\textbf{or}~S_{1, n_1} \ldots \\
I_1   \\
\vdots \\
I_{k-1} \\
\textbf{while}~C_k~\textbf{do}~\ldots S_{k, 1}~\textbf{or}~\cdots~\textbf{or}~S_{k, n_k} \ldots \\
I_k     \\
\end{array}
$$

where all the instructions in $I_i$ must always terminate and the loops $\textbf{while}~C_i$ have a non deterministic number of iterations, i.e. their condition $C_i$ "depends" on some select instruction inside the loop body.

This is true because the program is non deterministic and must be able to produce all numbers in $\mathbb{N}$, and so it must have at least one loop. Moreover this loop must have a non deterministic number of iterations otherwise it wouldn't be able to produce all naturals.

Now I'd like to argue that, if no compassion transition is allowed, then any such program could avoid executing the correct sequences of istructions $S_{i, j}$ that make the loop terminate and thus have an infinite computation.

However the whole thing seems rather ugly. Moreover it's not strictly true that such loops are at top level, they could be contained inside other loops that always terminate in a finite number of iterations etc. etc.

In other words I have big doubts on whether this is the correct way to go.

I believe there could be a proof that doesn't require considering the program structure at all but simply consider the possible runs of such a program and, by arguments about justice/compassion, argue that any such program must have an infinite computation.

Something like: consider the tree of all runs of such a program $P$. Since it is finitely-branching and its infinite then by Konig's lemma there must be an infinite run. Now (argument) so such a run is a valid computation and hence the program can diverge and it cannot be equivalent to $ANY{-}NAT$.

How would you fill the (argument) there? One thing that bothers me is that there could be infinitely many infinite runs, which, I find, invalidate some of the reasoning I'm trying to do about having a run from which an infinite number of finite paths must generate an infinite number of values.


texts: Addition, multiplication, and apostrophe used to represent boolean algebra expressions?

texts:
I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before.
I can make a guess that the apostrophe is equivalent to ¬ (except it's suffixed instead of prefixed). But I'm not sure what the addition and multiplication of the variables/propositional atoms would mean. Furthermore, I don't know how a boolean logic formula can "output" something other than just a truth value...
I can't seem to piece together with certainty the meaning of this representation. Could anyone take a look at the below example and maybe make a guess as to a translation of this representation to the more traditional ^, v, and ¬ symbols?
This arose in the context of digital logic in terms of logic gates and such on a CPU, if that makes a difference.

An alleged truth table of the above two expressions (the first row is filled in as an example):


texts: Creating PDA for {xy such that |x|=|y| and x ≠ y}

texts: I'm trying to create a PDA for $\{xy \mid |x|=|y| \text{ and } x \ne y\}$ over the alphabet $\Sigma = \{a, b\}$. But I don't know how the PDA will know if the two strings $x$ and $y$ are not equal. Please help me create this PDA step by step.


texts: Unambiguous formal grammars for a specific class of languages

texts:
Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$.
Now suppose that $q \in \mathbb{Q}$ is a positive rational number. Consider the language $L_q \subset \{0; 1\}^*$ of all words $w$, such that for any its prefix $p$ we have $\#_0(p) \leq q \#_1(p)$. For example, $L_1$ is the language of all possible prefixes of Dyck words.
It is not hard to see, that $L_q$ is deterministic context-free for any $q$. Indeed, if $q = \frac{m}{n}$ for some natural $m$ and $n$ we can build a following deterministic pushdown automaton that recognises our language. It has the following states:
State $0$: Reads an element from the input. If it is $1$, adds $m$ elements to the stack and remains in the State $0$. If it is $0$, moves to State $1$. This is both the initial state and the only final state.
State $i$ (for $1 \leq i \leq n-1$): Does not read input, but tries to read from the stack. If it succeeds, the stack has $1$ element less, and we transit to State $i+1$. If it fails because the stack was empty, we transit to State $-1$.
State $n$: Does not read input, but tries to read from the stack. If it succeeds, the stack has $1$ element less, and we transit to State $0$. If it fails because the stack was empty, we transit to State $-1$.
State $-1$: Reads input but does nothing. Nothing ever leaves this state.
Note, that this automaton is a final-state one. It stops when it attempts to read the input and finds that it has ended. It accepts the input if it stops in a final state.
From the fact, that $L_q$ is deterministic context-free we can conclude, that it is unambiguous. My question is:

How can we explicitly build unambiguous formal grammars for $L_q$ for arbitrary $q \in \mathbb{Q}$?

This question on MSE


texts: Finding the shortest path in a grid which has walls

texts: The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a magic wand which you can use $k$ times to destroy a wall. How do we find the shortest path from the top left corner to the bottom right?


texts: How does a prefix sum with 8 elements can be computed with three processors?

texts:
I would like to know if someone can give me an example of how a prefix sum which contains 8 elements can be computed with just three processors.

Prefix sum


texts: For a computational problem, can the set of instances be finite?

texts:
A computational problem consists of a set of instances. In most cases the set of instances is infinite. Like the set of all graphs, e.g.:

  Given a graph $G$, is there a Hamiltonian circuit in $G$?

Can the set of instances be finite and a problem still be non-trivial?


texts: Find amortized cost for insertion in binary arrays using accounting/potential methods?

texts:
Background:

The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. However, there will be no relationship between the items in different arrays. The issue of which arrays are full and which are empty is based on the binary representation of the number of items we are storing. For example, if we had 11 items (where 11 = 1 + 2 + 8), then the arrays of size 1, 2, and 8 would be full and the rest empty.
For inserts, we'll do them like mergesort. To insert the number 10, we first create an array of size 1 that just has this single number in it. We now look to see if $A_0$ is empty. If so, we make this be $A_0$. If not (like in the above example), we merge our array with $A_0$ to create a new array (which in the above case would now be [5, 10]) and look to see if $A_1$ is empty. If $A_1$ is empty, we make this be $A_1$. If not (like in the above example) we merge this with $A_1$ to create a new array and check to see if $A_2$ is empty, and so on.

Further clarification found here.

To be clear about costs, let’s say that creating the initial array of size 1 costs 1, and merging two arrays of size $m$ costs $2m$ (so merging the sorted arrays can be done in linear time).

The claim is that the above data structure has amortized cost $O(\log n)$ per insertion.

How to show this using the accounting and potential methods for amortization?
What would potential function be?

Initial ideas: Right off the bat it seems that this problem bears a lot of resemblance to the typical binary counter problem. Imagine each array being empty or filled represented by a value of 0 (empty) or 1 (filled), and these values are updated accordingly with insertions. These counters would change when current arrays are completely filled and have to perform merges, which will create a larger filled array and as a consequence several smaller unfilled arrays, changing a lot of 1s (filled) to 0s (unfilled). In the binary counter example the expensive cost of incrementing is dealt with through the potential function which is the number of 1s in the binary counter. The cost for an insertion here is not just incrementing a counter, but paying for costly merges. I do think the idea of a counter perhaps can tie into this problem, but am unsure how it connects to potential method and $O(\log n)$ per insertion. Any thoughts?
Also, found this explanation but it doesn't fully make sense to me. Maybe someone would be willing to elaborate?


texts: Reasons against Turing machines in proof complexity?

texts:
Turing machines were very successful in computability theory where Turing used them to resolve the Halting problem. His breakthrough led to proving that many other problems are algorithmicly undecidable. Key attribute of Turing machines is their infinite memory. However, natural complexity problems are combinatorial in nature and require finite memory and time.

In complexity theory, the infiniteness of memory has been addressed by forcing artificial bounds. We did not yet succeed in finding the right natural model of computation for time-bounded computations that would lead to breakthroughs in major open problems of complexity theory. I am particularly interested in natural computation models for proof complexity which does not involve explicit resource bounds.

  Why Turing machines may not be the appropriate model to resolve the NP vs CoNP problem? Are there any natural combinatorial models?


texts: I have read that a hardware interrupt is handled asynchronously by the CPU, which means that the interrupt signal may arrive at any point of time with respect to the CPU clock cycle. Now, this means that an interrupt may asynchronously hit the processor when it is in the middle of executing some instruction. So, how does the control pass to the OS in this case? For the case of software interrupts (exceptions), we know that the instruction being executed (trap instruction) itself is the cause of the interrupt. So, it will synchronously finish executing and then the control will transfer to the kernel as per the trap instruction nature. How does all this happen for hardware interrupts?


texts: Why does this pumping lemma proof not cover every division of xyz?

texts:
I am trying to prove $L =$ {${a^k|k=2^n, n \ge 0}$} is not regular.
So far I have identifed a string $s = a^{2^p}$, and I've divided $s$ into $xyz$ as follows:

$x = a^l$

$y = a^k$

*(where $k + l \le p$)

$z = a^{2^p-l-k}$

Now, when I start to look at pumping, I first select $i=0$:

$xy^iz = xy^0z = xz = a^la^{2^p-l-k}=a^{2^p-k}$, which is clearly not equivalent to $a^{2n}$. However, I know that there are mistakes in this proof and I have been told that my division of the string $s$ into $xyz$ does not account for all divisions. Could anyone please help?


texts: Best solutions to 6 degrees of separation

texts:
From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check whether A and B have 6 degrees of separation. If I simply wanted to check whether B is within 6 degrees I could also limit my depth to 6.

I have heard however that there are better ways of doing this using bidirectional methods which involve some heuristics. I was wondering if someone could explain the most effective way of doing this and compare space and time complexity between the different approaches. Thanks!

And as a followup, what would be a good algorithm for finding the degree of separation between two arbitrary nodes A and B and the path between them?


texts: Simple languages that are not of type-1?

texts:
To present interesting type-0 grammars to my students, I am looking for a very simple example of a type-0 language (=recursively enumerable language) that is not of type-1 (=not context sensitive). I am hoping for a language that is generated by a very small grammar, like two or three very short production rules or something like that.

The most simple examples I could think of so far:

The halting problem, or similar semi-decidable problems.
Any ExpSpace-complete problem, since these are not decidable in nondeterministic linear Space, which equals type-1 languages.
There are very small universal Turing Machines, but translating these into grammars gives a blow up again.

So for neither of these problems I see a simple way to encode them in a very short grammar or very small grammar.

Do you have any idea how to find such an example?


texts: Source and Destination IP of TCP connection

texts:
Five Tuple Identifier of TCP connection is (TCP, local IP, local port, remote IP, remote port).

I have made 3 computers in virtual box and set BOX1 for client, BOX2 for median, and BOX3 for server. And made interfaces between them to communicate.

So I have executed the server program on BOX3 and client program in BOX1. The client program calls 10.0.2.2.

When I captured packets from BOX1 and BOX3, the IP Source and Destination IP address was like this.

BOX1's SYN
Src : 10.0.1.2
Dest : 10.0.2.2

BOX3's SYN
Src : 10.0.1.2
Dest : 10.0.2.2

What I have thought is that in BOX1, Src must be 10.0.1.2 and Dest must be 10.0.1.1. And in BOX3, it must be 10.0.2.1 for Src and 10.0.2.2 for Dest. Because BOX1 communicates with BOX2 and BOX3 commuicates with BOX2.

Why does IP is like that?

Thanks for your help.


texts: Is there a canonical form that uses AND and XOR?

texts:
Is there something like the sum of products form of a circuit which uses AND and XOR instead of AND and OR?

I know that you can create an OR gate from AND and XOR (but i can't remember or find the details of that at the moment), but am wondering if there is anything more straightforward, as in an actual form that uses AND and XOR?


texts: Is best case complexity big Omega of worst case complexity?

texts:
I need to prove or disprove the following claim:

Given that the best case complexity of the algorithm A is $O(f(n))$ and the worst case complexity of A is $Ω(g(n))$, it follows that $f(n) ∈ Ω(g(n))$.

I know that obviously $A_b \leq A_w$.
I can also conclude obviously that for constants $c_1 , c_2$ and for all $n_0 \leq n$ for some $n_0$ the following happens:
$A_b \leq c_1f(n)$ and $A_w \leq c_2g(n)$.
I can see that it doesn't mean that $f(n) \geq cg(n)$ for some constant $c$ but I am having trouble disproving it.
Any help will be welcomed.


texts:
There's a formula given $$
 T(m,n) = \left\{
  \begin{array}{l l}
    1 & \quad \text{if $m=0$}\\
    1+T(n \mod m, m) & \quad \text{if $m>0$}
  \end{array} \right.$$
We're told to use repeated substitution to make a conjecture about a closed form for $T(F(n),F(n+1))$, where $F(k)$ is the $k^{th}$ Fibonacci number.This is a practice question and I have no idea how to start. Could someone help?


texts: Algorithm for placing objects inside a square from outside to inside

texts:
I have a map that is 300x300 units. I have to place squares of 20x20 units inside that map from outside to inside. There are 3 different types of square, the space available inside the map needs to be split equally to them, so from outside to inside the squares type 1 start to fill in the map until their limit is reached, then the square types 2 and 3 do the same until the map is fully filled with the squares.

Poor drawing example:

I apologize if I wasn't clear enough.


texts: Is complexity of $GI_{di}$ same as $GI_{un}$?

texts:
Does the graph isomorphism problem for directed graphs($GI_{di}$) reduce to the graph isomorphism problem for directed graphs($GI_{un}$)?

It is clear $$GI_{un}\leq GI_{di}$$ since the set of undirected graphs is subset of set of directed graphs. Does the converse hold true? That is, can an algorithm for undirected graphs used to test for problems in $GI_{di}$ with polynomial increase in complexity? Is $$GI_{di}\leq GI_{un}?$$


texts:
I am trying to learn CFG.  Now to make a CFG from a CFL it is really difficult for me.

Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem for generating a CFG. The Problem statement is to find a CFG that generates the following CFL: $$\{a^ib^jc^k \mid i,j,k\geq 0\text{ and } i\neq j\text{ or } i\neq k\}$$

Now I am trying hard to find one but I am not successful. Is there any easy approach to construct a CFG for a CFL?


texts: Get grammar from his LALR(1) parsing table

texts:
I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G?

Thanks :)


texts: Standard notation for the language of the universal Turing machine?

texts:
The universal Turing machine $U_{TM}$ is a TM that takes in as input an encoding of a TM and a string, then runs the TM on the string and does whatever the simulated TM does.  The language of the universal TM is the set of all encodings of a TM/string pair as a string for which the TM accepts the string.

I have seen several different names for the language of the universal Turing machine.  Michael Sipser refers to it as $A_{TM}$ (the acceptance language for Turing machines), while Hopcroft, Ullman, and Motwani call it $L_u$ (the universal language).

Is the a standardized term for the language of the universal Turing machine?  I would understand if there might be many "universal Turing machines" that vary in their encoding schemes, so if the answer is "no, there is no general term for this" that would be good to know.  I'm mostly asking because I'm teaching an introductory course in the theory of computation and have been using the term $A_{TM}$ for this without knowing if there is a better term to use.

Thanks!


texts: Calculating E(x) where it is the count of triangles in a special graph with n vertices

texts:
Assume we have n people with names: $h1, h2, ... , hn$ and they are going to shake hands with each other. The chance for every pair to shake hands is $0.6$.
define $T$ the count of distinct triads of handshaking at the end. every triad must have 3 people and every two of them must have shaken hands.
e.g. for $n = 4$ there are 4 different values possible for $T$.
$T = \{0, 1, 2, 4\}$
Note that there can't be any $T = 3$ for $n = 4$. As soon as you try to make the third triangle, forth one will be created too.
however you can be sure that $0 \leqslant T \leqslant  {n \choose 3} $ and for $n \geqslant 4$, $T$ can't be ${n \choose 3}-1$
how is it possible to calculate $E(T)$? ($E(T)$: Expected value of the random variable $T$)


texts:
Let's say we have a data set with following features
[age, sex, country, city, annual income]
[35, male, USA, New York, 73000].

I came across the article which explains how to deal with strings as an NN input.

Article example showing how to standardize data:

[0] 30  male    38000.00  urban     democrat
[1] 36  female  42000.00  suburban  republican
[2] 52  male    40000.00  rural     independent
[3] 42  female  44000.00  suburban  other

[0] -1.23  -1.0  -1.34  ( 0.0   1.0)  (0.0  0.0  0.0  1.0)
[1] -0.49   1.0   0.45  ( 1.0   0.0)  (0.0  0.0  1.0  0.0)
[2]  1.48  -1.0  -0.45  (-1.0  -1.0)  (0.0  1.0  0.0  0.0)
[3]  0.25   1.0   1.34  ( 1.0   0.0)  (1.0  0.0  0.0  0.0)

Now let's try to use this approach in our example where we could end up with thousands of different cities. We would have to create at least N vectors size of [1 ... N]. That approach just does not seem to be very efficient when we have unlimited number of possibilities.

That was a brief explanation of standardizing data problem. Now let me expand it to my specific NN task. I have a data set with 30+ features. Features consist of real numbers, decimal numbers, strings. All of them are relevant.

I have to transform non-computable data into numeric, NN computable form. The question is how to standardize a set of data with many features of different types (strings and numbers)?


texts:
I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix:
$$
\left[ \begin{array}{c}
- & A & B & C & D & E & F \\
A & 0 & 120 & 100 & inf & inf & 30 \\
B & 120 & 0 & 70 & inf & 150 & inf \\
C & 100 & 70 & 0 & 60 & 60 & inf \\
D & inf & inf & 60 & 0 & inf & 50 \\
E & inf & 150 & 60 & inf & 0 & inf \\
F & 30 & inf & inf & 50 & inf & 0 \\
\end{array} \right]
$$
Prim's algorithm will result in something like this:
$$
\left[ \begin{array}{c}
- & A & B & C & D & E & F \\
A & 0 & inf & inf & inf & inf & 30 \\
B & inf & 0 & 70 & inf & inf & inf \\
C & inf & 70 & 0 & 60 & 60 & inf \\
D & inf & inf & 60 & 0 & inf & 50 \\
E & inf & inf & 60 & inf & 0 & inf \\
F & 30 & inf & inf & 50 & inf & 0 \\
\end{array} \right]
$$

However, node A is now zoned and it will take at least 3 transitions from $A$ to get to $C$ and for my specific CSP I need at most 2 transitions. It is fairly easy to incorporate such CSP into Prim's algorithm. The question is: are there any generic algorithms which deal with finding a minimal spanning tree given a set of constraints ?


texts: Computing a shortest $M$-alternating walk (for the Blossom algorithm)

texts:
When explaining the Blossom algorithm for maximum (nonbipartite) matchings, Shrijver describes, given a simple graph $G = (V,E)$, a matching $M \subseteq E$, and the set $X \subseteq V$ of nodes missed by $M$:

  A walk $P = (v_0, v_1, \dots, v_t)$ is called $M$-alternating if for each $i = 1, \dots, t - 1$ exactly one of the edges $v_{i - 1}v_i$ and $v_iv_{i + 1}$ belongs to $M$. Note that one can find a shortest $M$-alternating $X-X$ walk of positive length, by considering the auxiliary directed graph $D = (V,A)$ with $$A := \{(u,v) \mid \exists x \in V : ux \in E, xv \in M \}.$$ Then each $M$-alternating $X-X$ walk of positive length yields a directed $X-N(X)$ path in $D$, and vice versa (where $N(X)$ denotes the set of neighbors of $X$).

(Walks are sequences of nodes which may contain duplicate nodes, and $v_iv_{i + 1} \in E$.)

I am not entirely clear on 1) the correspondence between $M$-alternating $X-X$ walks in $G$ and directed $X - N(X)$ paths in $D$, and 2) what exactly the algorithm is for finding the shortest $M$-alternating walk in $G$.

If a directed path in $D$ begins in $X$ and ends in $N(X)$, how does that uniquely correspond to a sequence of nodes which begins in $X$ and ends in $X$?

EDIT1: I now realize a directed path in $D$ need not begin in $X$, but it is my understanding that we consider only such paths to find augmenting paths in $G$.

EDIT2: I now also realize the answer is pretty obvious: if the path in $D$ ends on $N(X)$, that last node is neighbors with a node in $X$. Thus appending that neighbor to the walk yields an $X-X$ walk.
My first idea is to apply BFS from each node in $X$ to compute all shortest $X - N(X)$ paths (since $D$ is unweighted). Then, the path with the shortest length (number of edges) is the one we select to represent our shortest walk. This feels inefficient, but no alternative is specified in the text. Does anyone have an idea of what algorithm Shrijver may be hinting at here?

I understand asking multiple questions is frowned upon, but these are closely related.


texts: How to make smart contracts work in a small network?

texts:
Suppose we have a small computer network, there are 30 random people who have provided their computers to perform any computational tasks on them. Let's call these 30 computers nodes. We can access any of these 30 nodes arbitrarily, but by the condition of the problem, we do not know whether the node is honest. That is, we can not guarantee that the node will execute exactly the f (x) that we send to it, or that the node will certainly give us the correct answer.

Also, we have, by condition, A and B that want to conclude a smart contract with each other. A smart contract is a code (usually a small one, 15-25 lines long), whose body will certainly execute when a certain condition is set in the code.

In our case, the smart contract says that if event E1 occurs, B will pay A from its account, and if event E2 occurs, then A will pay B (how exactly will the payment in details not be discussed, it will occur within this network, using conventional cryptocurrency algorithms in the classic blockchain, for example).

The problem is that neither A nor B can guarantee if they entrust the execution of the smart contract code to a random node from our network that it will be executed correctly. One node can execute the received code in reverse or not execute at all. So which cryptographic algorithm A and B can use to ensure (statistically) the correct execution of the concluded smart contract? As already mentioned, they can use the services of any of the 30 nodes as you like.

I thought about dividing the smart contract into small parts and dividing them one by one into each of the 30 nodes, but how would this help if some dishonest nodes still execute their code incorrectly? We can easily find a dishonest node and exclude it, but a smart contract must be executed correctly the first time - that is, certainly, and not after the selection of honest nodes. When one of the nodes behaves incorrectly, the entire smart contract will already be executed incorrectly.


texts: How exactly do we define parametric polymorphism?

texts:
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:

In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$ T {...}

Whereas in ad-hoc polymorphism, we write different functions for each type:

Function f: Int $\to$ Int {...}
Function f: Bool $\to$ Bool {...}

But by that definition, we can always “pretend” to do parametric polymorphism:

Function f: <.Type T> T $\to$ T { if T == Int then {...}; If T == Bool then {...} }

How exactly do we define, from a type theory standpoint, parametric polymorphism, so that this is not allowed? Do we simply say that the term T is not allowed to be used in the body of $f$?
The reason I’m asking is: I am reading about the fact that parametric polymorphism allows certain nice guarantees that ad-hoc polymorphism doesn’t.


texts: Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?

texts:
In class, it was alluded to that a language: \begin{equation*}
\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}
\end{equation*} would be context free, if $L_1$ and $L_2$ are context free.

Intuitively, that doesn't make sense to me. I tried doing my own research and attempted a proof using the pumping lemma, but didn't get anywhere. Maybe I misunderstood? If that is correct, how could I prove it (or convince myself).


texts: Prove the languages |L| = 2 and |L| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

texts:
I am trying to prove the non-recursively enumerable property of two languages.

$L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and
$L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not= 2\}$.

My idea is to use the following two properties:

If A $\leq_m$ B and A is not Turing recognizable then B is not Turing-recognizable.
A $\leq_m$ B if and only if $A^c \leq_m B^c$.

For language $L_{2}$,
If I can show that $A_{TM}$ is mapping reducible to $L_{\not=2}$, according to property 2 we could get that $\overline{A_{TM}}$(the complement of $A_{TM}$) is mapping reducible to $L_{2}$, and for the fact that $\overline{A_{TM}}$ is not Turing recognizable, we could get that $L_{=2}$ is not Turing recognizable.

For language $L_{\not=2}$,
If I can show that $\overline{A_{TM}}$ is also mapping reducible to $L_{\not=2}$, and for the fact that $\overline{A_{TM}}$ is not Turing recognizable, we could get that $L_{\not=2}$ is not Turing recognizable.

However, I don't know how to prove the mapping reducible relationships between them. Or my direction could be totally wrong.

Could somebody give me the hints or possible solutions?


texts: If the branch predictor is placed in the fetch stage then how does it know that the current instruction is actually a branch before trying to predict its outcome? Is some (very little) decoding already done in the fetch stage before going to the actual decode stage?


texts: Reducing Halting Problem to Acceptor for TM

texts:
We have $A_{TM}=\{(M,w)|M$ is a TM, $w\in \Sigma^*_{TM},M$ accepts $w\}$

We intend to show that $HALT(M,w)\leq_T A_{TM}$ i.e. if we are given a machine for $A_{TM}$, we can decide whether $M$ halts on $w$ using it.

So, if $M$ accepts $w$, machine halts and we are done.

But if $A_{TM}$ says rejected how to know if $M$ halts?


texts: If a language has any single occurrence of a letter, is it not context-free?

texts:
From what I understand, the rules for CFL from my notes say:

If $L$ is a language and

• for all integers $N$,

• there is a string $w \in L$ of length greater than $N$ such that

• for all ways of writing $w$ as $uvxyz$ with ($v \neq \epsilon$ or $y \neq \epsilon$),

• there is an $i$ such that $u(v^i)x(y^i)z$ is not in $L$,

then $L$ is not context-free.

Does this mean that if we have any equation like:
$L = \{a^m b a^n \mid m = n\}$, then we can use this for example:
$u=a^m, v=b, x=a, y=a^{n-1}, z=null$

Where we any value of i greater than 1 would make the equation invalid?
This gives us $a^m(b^i)(a)((a^{n-1})^i)$ where $b^2$ means that there are two $b$'s, a string that's not accepted in that language.

However, in this case, then a Language $L = \{bcde \mid b = c = d = \epsilon\}$ could be proven as not context free. What am I misunderstanding here?


texts: I want to create a new way of representing floating point. In standard IEEE floating point, we have 1 bit to represent sign, 8 bits to represent exponential and 23 bits to represent significand. In the new floating point system, I keep the breakdown of sign/exp/significand but there is no implicit 1 (assume there is no denormalized numbers). For example, in this new scheme to represent 3, we have sign bit 0, exponential bit 0x7F and significand 0x000003. Does this new system of floating point represent a larger unique numeric values than IEEE standard point? My thought is that since both systems have the same breakdown they represent the same number of unique numeric values


texts: Matching Lemma with infinitely many symbols

texts:
I was reading about Universal Turing Machines.

I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number of ones.

This is used to match strings of ones between two tapes.

Now I wonder, would there also be a TM or a method of implementation of a TM which can match two strings? To me it intuitively appears, that inifinitely many symbols implies infinitely many states for the machine, and an example workflow may look like:
found symbol X, enter state stateX, exit stateX to state readnextchar if again X was found on the second tape.

Would that not mean an infinitely long transition table? or is there an way to represent a table in a smaller way?

if the symbols are represented via some kind of place value system, e.g. decimal, binary, would that shorten the transition table length?


texts: Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

texts:
This is a question from an exam I did today:

  Given $M$, a turing machine, we need to decide the following:

  1) $M$ halts on every input

  2) The language of $M$ is CFL

My question is, can I prove that this problem is not in $RE$ (recursively enumerable) using Rice's theorem? I understand that Rice's theorem works for languages and not machines, and when first looking at it, number 1 is a property of a machine not the language. But what I said, is that actually it is a property of a language: $M$ halts on every input iff $L(M)$ is decidable! (in $R$), so we can use Rice.

What do you think?


texts: Is there any way to "pre-compute" a huge dataset in order to make *any* arbitrary linear-time computation on it sub-linear?

texts:
Suppose that you have a huge (terabytes worth) collection of numbers, and you know that you will, in a future, need to run some statistics of it. In order to cut future work, you notice that, by pre-computing some key statistics, you can make other statistics be computable in sub-linear time.  For example, if you store the sum and the length of the collection, you can, in a future, compute the average in linear time. If you also store the variance, you can compute the standard deviation. You can keep adding specific statistics in hope to cover as many "future computations" as you could.

My question is: is there any way to prepare the dataset such that any arbitrary linear-time function could, in a future, be processed in sub-linear time? In other words, is the snippet below possible?

# builds an ideal pre-computation of an arbitrary bit string
precomputed = precompute(arbitrary_bit_string)

# builds a circuit for a "countOnes" function
# could be any other arbitrary linear-time function
countOnes = buildCircuit("... an String->Int algorithm here ...")

# computes the number of ones in sub-linear time
average = execute(precomputed, countOnes)


texts: What is the strongest weaker version of the halts() function?

texts:
I was wondering about some questions related to the Halting problem. I might have not understood all the assumptions in it fully. Would you kindly help me, please?
I understand that the construction in the proof leads to a contradiction. My thoughts are:

If one runs these theoretical programs in the real world, I would expect that the output of halts(f()) will oscillate between true and false with a frequency dependent on the processing speed. This all happens because the execution of f() is made dependent on the output of halts(f()). Self-referenced.

Obviously there are programs which do not need to be run by a testing halts() function and they can be still decided if they halt or not. For example the following will obviously not halt and there are IDEs which already detect it:
while(true)
;

Based on the previous 2 thoughts, can we state that there can be such halts() program that tells us if a program halts or not and oscillates between the two values only if the input program code takes the output of a halts(f()) function as an input in the inside?

Such halts() is still useful. Even if it cannot tells us a certain answer for a constructed, self-referenced pathological case.
Basically I am trying to figure out what is the strongest weaker version of the halts() function. What can we expect from it?


texts:
I am self studying discrete math and I am going through MIT Mathematics for CS lecture notes but they do not have solutions available. I got stuck at Problem 3.14 (pages 64-65 of this document). The problem is about the construction, given an arbitrary propositional formula $F$, of a proposition $C(F)$ such that:

$C(F)$ is in 3-conjunctive form (3CF), i.e. it is a conjunction of disjunctions of at most literals (a literal is a variable or a negation of a variable);
$C(F)$ has at most 24 times as many occurrences of variables as $F$;
$C(F)$ is satisfiable iff $F$ is.

The idea is to introduce a new variable for each operator that occurs in $F$. For example, given
$$ F_1 = ((P \oplus Q) \oplus R) \vee (\neg P \wedge S)) $$
assign $X_1, X_2, O, A$ to the 4 operators in $F_1$, and define four constraining formulas:
$$ \begin{align*}
 C_1^1 &= X_1 \Leftrightarrow (P \oplus Q) \\
 C_1^2 &= X_2 \Leftrightarrow (X_1 \oplus R) \\
 C_1^3 &= A \Leftrightarrow (\neg P \wedge S) \\
 C_1^4 &= O \Leftrightarrow (X_2 \oplus A) \\
\end{align*} $$
and $C_1 = C_1^1 \wedge C_1^2 \wedge C_1^3 \wedge C_1^4 \wedge O$.

The questions are:

Why is $C_1$ satisfiable iff $F_1$ is satisfiable?
Why is each constraining formula equivalent to a 3CF formula with at most 24 occurrences of variables?
Generalize from the example to construct $C(F)$ for an arbitrary formula $F$.

For question 1, I don't see why $X_1$ is satisfiable.

I think question 2 is wrong, beacuse you can form a 3CF formula with at most 24 occurrences of variables, only if you have a 3-conjunctive normal form but here the author only says 3 conjunctive form.

(For 3CNF, 8 different triple terms can be formed using 3 variables with a total of 24 variables, For 3CF, 26 different single,double and triple terms can be formed with a total of ? variables.)

No idea about question 3.


texts:
have a question regarding rectangular automata and their derivatives.

In each location the derivates are defined by a interval, how are the derivates applied on the variables?
Is one value chosen out of the interval and added to the value or do we reset the value to one value in the interval ?

Regards


texts: Why is the complexity of factorial a function of n?

texts: When we compute the complexity of calculating factorial of a number $n$ why is it in terms of $n$ instead of the number of the number of bits occupied by the number of bits occupied by $n$ (like we do in number-theoretic algorithms like primality checking etc.)?


texts: Guided mining of common substructures in large set of graphs

texts:
Disclaimer: I'm not a CS so I basically have no idea what I'm talking about

I have a large (>1000) set of directed acyclic graphs with a large (>1000) set of vertices each; the vertices are labeled.

I want to identify substructures that appear frequently over the whole set of graphs.

A substructure is a graph of at least two vertices with specific labels. Such a substructure may appear once or more in one or more of the given input graphs. For example "a [vertex labeled A with two children labeled B] appears twice in graph U and once in graph V".
A substructure must obey a set of pre-given rules which filter on the vertices' labels. As an example: A substructure that contains a vertex label A is interesting if the sub-graph is "a vertex labeled A that has at least one child labeled B and is not a sibling of a vertex labeled U or V". Substructures that do not conform to these rules may appear in the input graphs but are not of interest for the search.

I have tried to look into things and (as it seems to always happen with me) the problem is NP-complete. As far as I can see gSnap is the most common algorithm to solve this problem. However, as stated above, I'm not looking for any common substructure in the graphs but only those that obey certain rules. One should be able so use that in order to reduce the search space.

Any insight on how to approach this problem?

Update: I should probably add that the aforementioned rules can be recursive. For example "a vertex labeled A with at least two children labeled B, each having at least one child labeled A". Besides practicability there are no limits on recursion depth.


texts: Is there a paradigm for composing "incremental update" functions in a pure dataflow style?

texts:
I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me.

Background, just so we're on the same page: Programs often contain caches - a time/memory tradeoff. A common programmer's mistake is to forget to update a cached value after changing one of its upstream sources/precedents. But the dataflow or FRP programming paradigm is immune to such mistakes. If we have a number of pure functions, and connect them together in a directed dependency graph, then nodes can have their output value cached and re-used until any of the function's inputs change. This system architecture is described in the paper Caching In Dataflow-Based Environments and in an imperative language it's more or less analogous to memoization.

Problem: When one of the inputs to a function do change, we still have to execute the function as a whole, throwing away its cached output and re-calculating from scratch. In many cases, this seems wasteful to me. Consider a simple example that generates a "top 5 whatever" list. The input data is an unsorted list of whatever. It's passed as input to a function that outputs a sorted list. Which in turn is input to a function that takes the first 5 items only. In pseudocode:

input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)

The complexity of the sort function is O(N log N). But consider that this flow is used in an application where the input only changes a little bit at a time, by adding 1 element. Rather than re-sorting from scratch every time, it would be faster, in fact O(N), to use a function which updates the old cached sorted list by inserting the new element in the correct position. This is just one example - many "from scratch" functions have such "incremental update" counterparts. Also, maybe the newly added element won't even appear in the final_output because it's after the 5th position.

My intuition suggests it might be possible to somehow add such "incremental update" functions to a dataflow system, side by side with the existing "from scratch" functions. Of course, re-calculating everything from scratch must always give the same result as a doing bunch of incremental updates. The system should have the property that if each of the individual primitive FromScratch-Incremental pairs always give the same result, then the larger composite functions built from them should also automatically give the same result.

Question: Is it possible to have a system/architecture/paradigm/meta-algorithm which can support both FromScratch functions and their Incremental counterparts, cooperating for efficiency, and composed into large flows? If not, why? If someone has researched this paradigm already and published it, what is it called, and can I get a short summary of how it works?


texts: Why is the array used for a restricted hashing scheme always sized to a 4k + 3 prime? When they talk about a restricted hashing scheme are they talking about a non perfect hashing which includes having a collision algorithm which resolves that problem? Can someone please help me?


texts:
Given a recursive function $T(n)=T(a_1\cdot n)+\dots +T(a_k\cdot n)+\Theta(n)$ such that $\forall a_i: 0<a_i<1$, what is the most general thing I can say about the sum of the cost of the nodes at each level of the recursion tree?  I've looked at a few, and for the ones I've looked at it's always come out to $(a_1+\dots +a_k)^i$ where $i$ is the level in the tree.

Could anyone explain this?  If it matters it's in the context of trying to prove that $T(n)=\Theta(n) \Leftrightarrow a_1+\dots +a_k < 1$


texts: PSPACE-complete problems can't be in NL using the space hierarchy theorem?

texts:
I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this :
From the time hierarchy theorem I know that for every $t(n)$ there exists a language that is decidable in $O(t(n))$ space but not in $o(t(n))$ space. Then I want to assume that there exists $A \in PSPACE\text{-complete} \land A \in NL$ and take a language $L$ that is decidable in $O(n)$ time but not $o(n)$ time, reduce it to $A$, reduce it to $PATH$ and get that through that reduction $L$ is decidable in $\Theta (log(n)^2)$ time, a contradiction.

However my reasoning fails in that the reduction from $L$ to $A$ isn't necessarily a log-space reduction. What am I missing? How do I overcome this?


texts: Find lines segment portions close together

texts:
I have two lines segment in 3D space. Lines segment are defined by 2 points each: $A_1$, $B_1$ and $A_2$, $B_2$ (see left part in the below schema).

I would a like to find an algorithm to detect which portion of the line segment 1 has a distance less than or equal to $x$ to the line segment 2 (and the opposite). The expected result of the algorithm is represented by the red lines in the schema:

Could you please provide me some tips & tricks? I do not know where to start. Thank you.


texts: How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?

texts:
$L = {a^n + b^m + a^{n+m}}$
This is the language I want to show is not regular.
Now my problem is to choose p correctly.
Can I just set it as p=2*(n+m) ?
That's the problem I am facing now.
Thanks for any help I am starting to learn it to use the pumping lemma.
Edit:
In the meantime I have done this:
$w=a^nb^ma^{n+m}$
|w|= 2(n+m)=p
$|xy|\leq 2n + 2m$
We choose $x=a^n, y=b^m, z=a^{n+m}$
$|a^nb^m|=nm \leq 2n+2m$
w=xy^iz
Now we set i = 0
$w_0=a^na^{n+m} \notin L $
$\implies $ L is not regular.


texts: textbook on the human brain for computer scientists/machine learning professionals?

texts:
The human brain as studied by neuroscientists, or neurobiologists, generally focus on what I would call

implementation details (how specifically does information transport between synaptic channels, i.e. what are the chemical processes)
vague generalities (e.g. about "memory" as a psychological concept and in very vague terms what types of memory there are without studying them mathematically)

There is nothing intrinsically wrong with this.

But I am interested in the brain as a computational system. Of course we don't yet understand the brain very well, but is there a book on the brain that a computer scientist or machine learning professional could read to get a computational/systematic understanding of what we know about the brain? e.g. what is the computational role of various neurotransmitters (without going into chemistry), etc.


texts: Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

texts:
The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford algorithm can work with and detect -negative edge cycles.

However I feel a bit different, especially after coming across problem asking to build shortest path tree from node $a$ in following graph:

My shortest path tree after running Dijkstra came like this:

Then why texts say that Dijkstra need all non negative edge weights?
I feel that it should be no -ve edge weight cycle reachable from source node.
Am I correct with this? or am I missing something here?


texts: Intuition behind Floyd-Warshall being faster

texts:
I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm:

  Let $dp[i][j][n]$ denote the shortest path from $V_i$ to $V_j$ using at most $n$ vertices. Use $dp[i][j][n] = \min_{V_k\text{ adjacent to } V_i} (e_{ik}+dp[k][j][n-1], dp[i][j][n-1])$ to compute all values of $dp[i][j][n]$.

This above algorithm runs in $O(EV^2) = O(V^4)$, and it's clearly slower than Floyd-Warshall. But I don't intuitively see why that should be the cases (since both look pretty similar) -- i.e what this algo is doing "dumbly"/recalculating which is useless/can be speed up.

Can somebody provide some intuition for why this is slower ? Or in general intuition about why you should expect to find all pair of distances in $O(V^3)$, not in something like $O(V^4)$ or greater ?


texts: Approach / data structure to wait for N tasks to complete in arbitrary order

texts:
My system needs to wait for the completion of N tasks and terminate when all are completed. The work items are passed in as an immutable array and the execution of these items are handled externally to my system. Checking for completion is quite inexpensive and the items can complete in any order. The size of these lists are relatively small -- in the hundreds or thousands of entries, so memory size is not an issue. Given the constraints of the system, the task list passed in is an immutable array so anything I'd want to do with that would need to augment or copy it. In case it's relevant, I'm using C++17.
A simple (naive?) approach to this would be to create a boolean array of completion status (initialized to false) and mark the corresponding index in that array as true once the work item has been completed. Then, iterate through the task list again and again until all items are completed.
Of course, with this approach, towards the end of the run there will be a lot of checking of the completed list with little actual work to do (and on average, the algorithm will go through half of the entries that have already been done).
Another approach would be to create a singly-linked list of array indicies (initialized to the elements [0, N)) and remove elements as work items are completed. That avoids the "wasted checking" approach of the parallel completed array approach mentioned above; it would just jump directly to the indices in the task list that are not known to already be completed.
It seems that there may be a faster / elegant approach to this, though, or a data structure that naturally handles this.


texts: Extended stars and bars approach using dynamic programming

texts:
If we have an equation with N variables of the form x1 + x2 + x3 +...+ xN with sum S, and upper and lower bounds for each of the N variables, is it possible to find the number of integer solutions (ways) to solve the problem ?

For eg :- if S=5, N=3 and the bounds for variables are 1<=X<=3, then combinations possible are (1,1,3) , (1,3,1) , (3,1,1), ( 2,2,1), (1,2,2), (2,1,2).

It's easy to find the number of ways without the bounds (upper and lower) using combinatorics. But is there any way to find the number of ways in such a case in O(S) or O(N) ?


texts: How to use dynamic programming to solve this?

texts:
Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies and toonies you have. Assume that you have enough coins to pay x cents. You do not have to pay exactly x cents; you can pay more. The cashier is assumed to be smart enough to give you back the optimal number of coins as change. We want to minimize the number of coins that changes hands, that is the number of coins you give to the cashier plus the number of coins the cashier gives back to you.

For example, if we want to pay 99 cents and we have 99 pennies and 1 loonie, then the optimal solution would be to give the cashier the loonie and take back 1 penny.

A particularly easy solution that occurs to me is to create a six-dimensional array. But in practice this is not feasible. So I am wondering if anyone can give me a small hint as to how to use dynamic programming to solve this (as this question looks intuitively to me like a DP problem). Once I have a hint, I can perhaps work out the remaining details myself. Thanks.


texts: Help in geometrically understanding "Linear Decision Trees"

texts:
In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes the intersection of the half-planes deﬁned by the nodes touched by the path."

I fail to visualize how path tracing is done? I would be glad to see it explained through the presentation of the path in a 2-dimensional space.

I do understand that $x_1,x_2,...,x_n$ is a point in the $R^n$ dimensional space. But I don't get how Figure 17.1 in (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf) helped in proving the lower bounds of Element Uniqueness as $\Omega(n\log n)$. I also don't get the implication of $\#F$ being connected components; why can't they simply be called solutions?

Unfortunately, reading online resources did not help me much understand the aforementioned concepts.

Thank you in advance.


texts: Prove correctness of the iterative algorithm

texts:
Description:

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Code:

class Solution {
    public int removeElement(int[] nums, int val) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[count++] = nums[i];
            }
        }
        return count;
    }
}

The problem may seem very simple but the solution I came up with is quite intuitive and hence it may be prone to errors in situations like interviews, I would like to know if there is some sort of formal check for the correctness? if yes then, is there any generic approach?


texts: Why is it that the flow value can increased along an augmenting path $p$ in a residual network?

texts:
I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement:

  the flow value can increased along an augmenting path $p$ in a
  residual network

I was reading the slides linked at the end of question and they seem to omit the most important part of the algorithm which is proving the above claim!

Recall how a residual network is built (which can be referenced on chapter 26 of CLRS):

$$c_f(u,v) = \begin{cases}
      c(u,v) - f(u,v) & if (u,v) \in E, \\
      f(v,u) & if (v,u) \in E \\
      0 & otherwise.
   \end{cases}
$$
also recall that because we don't allow self loops of length 1 or 2 (i.e. if $(u,v) \in E \implies (v,u) \not \in E$, exactly one case in the above definition of residual capacity applies.

I understand that intuitively, the first case encompasses the idea of the additional flow that we can increase in the original graph (since it encompasses the amount of extra flow we can increase) and the second case is suppose to be included for allowing our algorithms to decrease the flow.i.e. sometimes it may be necessary to actually decrease the flow in some edge(s) (or increase the flow in the opposite direction) so that the overall flow increases.

Even though this ideas are clear to me, its not clear how its guaranteed that we can actually increase the overall flow in the original graph $G$ if we choose say, the minimum residual capacity in an augmenting path. In particular, its clear to me if the path only contains edges of case 1 (since increasing the flow along such a path just means increasing the flow such that we are still bellow the capacity, so its trivial to increase the flow), but the second type of edge make it confusing for me. How is it that those edges guarantee the following:

The flow increases overall
No conservation law is broken (flow in = flow out is still obeyed)
No capacity constraint in the original graph is obeyed.

Not sure if there are other properties to check but those are the ones I was able to think of.

This is what I have so far:

Let the smallest residual capacity be $c_f(p) = \min_{(u,v) \in p} \{ c_f(u,v) \}$. If we increase the flow according to it then its clear no capacity constraint is violated. Why? There are only two type of possibilities the edge could have come from:

1) The difference between a capacity and a flow
2) The opposite direction of a flow already on the network.

Consider case 1 first. If we increase the flow, then it means that we decrease difference of the capacity and a flow (i.e. the residual capacity). If this is the case, since we choose the smallest residual capacity as the amount to make the decrease, we don't risk increasing the flow to much because an increase will correspond to a increase in flow such that the flow is less that the capacity on the real network.

If on the other hand, if the edge came because it corresponded to the opposite direction of flow of an edge, then its even easier, because that means that the flow on the original graph will correspond to a decrease not an increase. Since we are decreasing we cannot violate a capacity constraint. Furthermore, since we are choosing the smallest decrease to be made, there is not risk of the flow randomly becoming negative in the original graph (which would correspond to non-sense). Hence, this can't happen either.

Therefore, the capacity constraints are not violated by this choice of change of flow on the network.

The other two conditions, seem a little harder to check. I am sort of stuck on the other two but will keep trying and if I make progress (or not) update the question.

I am learning flow form the following slides based on CLRS:

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-Spring15-trunc/Network-Flow-Spring15-trunc.pdf

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-II-Spring15/Network-Flow-II-Spring15.pdf


texts: Reachability queries on uncertain graphs

texts:
We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?


texts: I want to split my data into $n$ approximately equal parts. Which simple hash functions will ensure that the number of $x$ with $h(x)\equiv i\pmod{n}$ is approximately equal for each $i$?


texts: Context free grammar to Chomsky's normal form

texts:
\begin{align*}
S&\to AACD\\
A&\to aAb\\
C&\to aC\mid a\\
D&\to aDa\mid bdb\mid\varepsilon
\end{align*}

I think that this grammar is infinite so it is not possible to convert it into cnf. Am I correct ?


texts:
I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^j)\right) $

when I searched online, I saw people have solved this as below:

$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $
$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
$T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
$T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

$ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
There is a small o in equation 4, then how can we write theta in equation 5.


texts:
Measure words (aka classifiers) are used in Chinese to "measure" things, e.g.

三杯牛奶
Three glasses of milk
那个人
That person
一只乌鸦
One crow
一公斤豆腐
A kilo of tofu

We don't have an equivalent in English [they're not collective nouns (e.g. a murder of crows)].  It'd help reading Chinese text to be able to highlight measure words in a distinct color.
Thus, I'm interested in the following problem:
Input: Chinese plaintext.
Output: Identification of which characters are measure words in that plaintext.
It's a highly restricted version of Chinese text segmentation, and I expect it would be substantially simpler, e.g. there's only a short list of characters which can be measure words.  It may even be considered "solved".
However, there's some nuances which make this challenging, e.g., repeated measure words e.g. 个个 and 一根根, and characters in measure words can also belong to Chinese words, e.g. 个人, 家庭.  Nevertheless, there may only be a small number of exceptions here.
Question: How to identify measure words in Chinese text?
Searching for Chinese measure words in ACM didn't give anything relevant, but this problem may have arisen as a sideline in other work on Chinese text segmentation.


texts: Doubts on the behavior of Unit Type in a type system

texts:
I have a doubt about the Unit Type in the context of Type Theory and its use in different case scenarios.

To start with, a Unit Type can be seen as a nullary Product Type, namely Unit, with one only value term which is the empty tuple, (). Also, there exist a unique map from any type to the Unit.

Now, it happens that the use of the Unit Type goes beyond such trivial definition, and is in fact used in the definition of Algebraic Data Types, which are Sums of Product Types. Specifically, it is possible to represent the concept of an Enumerated Type using a Sum of Unit Types, e.g. in StandardML we might have:

datatype suit = HEARTS | CLUBS | DIAMONDS | SPADES

where HEARTS, CLUBS, DIAMONDS and SPADES are nullary Product Types and therefore all isomorphic to the Unit.

My doubt is the following: if there exist only one element of Unit, how can the type system distinguish between the four distinct instances used in the Sum Type above (five instances if we also consider the empty tuple...)?
I understand that they can be considered all equal to each other up to isomorphism, but they are extensionally different and in fact, even by considering only the suit we are supposed to pattern-match on them...


texts: Can someone explain why the MAX-CUT problem is in NP?

texts:
Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges
have one end in each subset?

I'm a little confused on showing how the problem is NP, in terms of a certificate and certifier.


texts: Dynamic job scheduling with earliest time and deadline

texts:
I have a real life algorithmic problem and I'm trying to find out if there is any similar widely known algorithmic problem with known solutions that I could adapt to my particular use case.
I want to solve a kind of scheduling problem: I have a machine that will be processing jobs and I want to fit them into a schedule.
The capacity of the machine is limited within discrete time units (for example hours). During every given time unit $t$ the machine can process a limited number of work units - $u(t)$.
There are job queries coming one by one (they aren't all known upfront), each job $j$ has:

the earliest time it can start to be processed by the machine $j_{et}$ - so it can only be processed if $t \ge j_{et}$
the deadline $j_{ft}$ when it has to be finished - so it can only be processed when $t \lt j_{ft}$
number of work units it takes to process it - $j_u $

The job has to be finished "in one go" - once a job is started by the machine the job has to be finished before any other job is started.
For each incoming job query I need to be able to:

tell if it is possible to add the job to the schedule or it has to be rejected
add the job to the schedule if possible

The closest problems I've found are:

"Job Sequencing with Deadline"
but in case of this problem jobs are known upfront (so the algorithm is static) and some of them may not meet the deadline.

"Multiprocessor scheduling"  which in case of identical processors references "Multiway number partitioning"
but as I understand they seem to be more focused on separating the job between multiple processors while in my case I have only one machine.

Is there anything 'closer' to what I described? I would appreciate any hints or references that could inspire me solve this particular problem.


texts: Minimum distance between two convex hulls maximized

texts:
I want to implement a program that splits a set $S$ of $n$ points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized.

It should be done in $O(n^3)$.

I have several ideas but I'm not sure whether they are correct:

I sort points by $X$ and then for each two points I find the distance but only if there's no any other point between them. Then I choose the closest point to the first one on the left and the closest point to the second one on the right (first point would be part of the first polygon and second one of the second polygon).

Then I find distance between point and line, line and line, line and
point and point and point(but I already know that). That's how i
find the maximal distance and then with Graham scan I create a
convex hull. I repeat everything for $Y$, because maximal distance
could be on $Y$, not on $X$.
I sort points by $X$ and then create a convex hull for first $3$ and another convex hull for other points. Then find a minimum distance between these two hulls. I save the distance and if it's greater than distance i saved before I overwrite it and remember polygons. And last step is when only $3$ points are left for the second convex hull. Then I do all these steps for $Y$.

What do you guys think about my ideas? Do you have any improvements or maybe another, better idea?


texts: How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming?

texts:
I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by absolute differences.

Example:

Numbers: 1 2 3 4 5 6 7 8 9 10, need to divide into 3 groups.
Let's say we want to minimize sum of absolute differences (SAD).
Groups: (1) 1 2 3 4 5 6 (sum = 21); (2) 7 8 (sum = 15); (3) 9 10 (sum = 19)
Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 <- That's what we want to minimize.

The question is how to solve it using dynamic programming?

The original question - https://stackoverflow.com/questions/9275280


texts: What advanced math topics are recommended for computer science?

texts:
I am enrolled in a computer science degree at the moment. I have looked around trying to find answers, but people tend to ask 'what is the minimum math needed for computer science' as opposed to what is recommended. I am very interested in theoretical computer science topics. My interests sort of jump around but right now I have a distinct interest in cryptography.

I have always loved math. In high school I did advanced math units - equivalent to calc 1 & 2, as well as discrete math. Right now I am doing a linear algebra unit and a calc 3 unit (as well as my cs units). Next semester I will be doing a unit on number theory. But what else? What other units would actually help with computer science? For example, I can't imagine learning about differential equations would be applicable to computer science.


texts: $n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

texts:
I have this problem

  A ﬁrm has $q_j$ jobs of type $j$, where $1 \leq j \leq  n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of running machine $i$ is $f_i +m_i·q$ where $f_i$ is the ﬁxed cost of running the machine and $m_i$ is the marginal cost of servicing one job on the machine (thus $m_i·q$ is the marginal cost of servicing $q$ jobs). Assume that $f_1 ≤ f_2 ≤ ···≤ f_n$ and that $m_1 ≤ m_2 ≤···≤ m_n$. The ﬁrm wishes to ﬁnd a subset of the machines that can service all the jobs at the minimum total cost. Show how this problem can be formulated as a shortest path problem.

I assume, possibly will have to show, that the $q_j$ jobs of type $j$ are all done by the same machine.
Here is one of the most promising attempts that I got so far:

Here is the first graph implementation

So basically, we have a directed tree going from right to left. At the level 0 edge, are done $q_n$ jobs of type $n$ by the machine $[n]$ and on the edge is the cost of this operation.
Further, for completing the $q_{n-1}$ jobs of type $n-1$, we can choose either the machine $[n]$ or $[n-1]$ with the associated costs over the edges. And so on.
The problem is that already at the level 4, if I use the machine $[n-1]$ for completing $q_{n-3}$ jobs of type $n-3$ after using machine $[n-2]$ I don't know if the machine $[n-1]$ was used before. So I don't know beforehand the cost of taking the edge between $[n-2]$ at level 3 and $[n-1]$ at level 4.

The same problem is highlighted at the level 5 for the machine $[n-2]$ by two zigzagging paths, one using the machine $[n-2]$ and the other avoiding it.

The number of edges of this tree has a growth of order $n^3$ and the number of vertices has a growth of order $n^2$. So this solution still looks feasible if we manage to patch the mentioned problems.

  So here are my questions:

What is the common name given to this class of problems? (if it exists)
How can my solution attempt be fixed? (if it can be done)
Otherwise, how the problem can be solved?

Thank you very much in advance for your time and help!


texts: What does the symbol "::" mean in computer science?

texts:
What does the symbol $::$ mean in the following statement?

$\forall{x}\in K :: x \longrightarrow x$

A cycle in a graph is a path that starts and ends on the same node.
Clearly, if nodes in K lie on a cycle, then $\forall{x}\in K :: x \longrightarrow x$.

Look at page 56 in the following.

https://books.google.co.in/books?id=nel4vdeLcqkC&pg=PR7&source=gbs_selected_pages&cad=2#v=onepage&q&f=false


texts: Prove correctness for computing the nth Fibonacci number for the pseudo code

texts:
How do we prove the correctness of this pseudo code by induction?

fastfib(integer n)
if n < 0 return 0;
else if n = 0 return 0;
else if n = 1 return 1;
else a ← 1; b ← 0;
   for i from 2 to n do
       t ← a; a ← a + b; b ← t;
return a;
end


texts: How to prove that there is no better algorithm

texts:
Input: Set of machines M, Each machine has an availability array D_m[t],
set of activities A, for each activity j its starting time s_j,
its duration p_j and its consumption in D during processing.

Output: True or False if the usage for  each machine at each instant is less than the availability

for each machine m in M

  usage := array[0..L] of zeros

  for each activity j in A
    usage[s_j] += c_{j,k}
    usage[s_j + p_j] -= c_{j,k}

  for each time t in [1, L]
    if usage == 0
       usage[t] += usage[t-1]

  for each time t in [0, L-1]
    if usage[t] > D_m[t]
      return false

return true

The complexity is $O(|M| * (L + |A|))$. But $L$ is not an input length, it's a numerical value. I guess it's pseudo-polynnomial (Am I right ?)
How to prove that there is no better alternative, In other words that its also $\Omega(|M| * (L + |A|))$


texts: I have an assignment to construct a game of Nim (a game in which two players must divide a pile of tokens into two unequal sizes; 6 can be divided into 2 & 4 but not 3 & 3). I was provided a game tree (the same one I find on Google), but I am confused. Shouldn't the first turn of the second player have access to S6, S5, and S4 and S3 since 7 can be divided into 4 & 3?


texts: Efficient Algorithm for Combinations With Replacement (n choose k)

texts:
I am looking for the canonical implementation of the "k-combinations with repetition" algorithm.

Simple Example:

Input: "ABC" (choose 2)

  ['AA', 'AB', 'AC', 'BB', 'BC', 'CC']

I have a recursive implementation, I'm looking for the performance optimized state of the art version.  Usually people mention Knuth for this, but I haven't seen a specific reference to Vol 4a or otherwise for this particular one.  Not to say it isn't there, just haven't found any references to it.

Where might I look further into this?


texts: How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?

texts:
BACKGROUND:

Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will).

Assumption: Just for the sake of this question, let's assume that the term "basic operation" means an addition or a multiplication operation between two single-digit numbers.

Now we have to calculate the number of basic operations involved in the simple multiplication (the one we learnt in 3rd grade) of any two numbers, provided that both the numbers have the same length (i.e. the number of digits).

Let's say n represents the length of the numbers.

Let the numbers be 1234 and 5678. The following image shows the multiplication:

As you can see, each row (i.e. each partial product of the first number with a digit of the second number) involves 4 multiplication operations, and 4 addition operations (think of the carries). Depending on the number of carries (and thus depending on the original numbers), in the case of any two numbers, in each row, it could be at least 0 additions (no carry) and at most 4 additions (a carry from each digit-to-digit multiplication).

In other words, each row involves ≤ 2n operations. As there are n rows, so the basic operations in all the rows are n(2n), or 2n2.

QUESTION:

Now comes that one final addition (shown in black pen in the image). From the video lecture

  The final addition requires a comparable number of operations.
  Roughly, say, another at-most 2n2 operations.

The question is

What is meant by "comparable" number of operations?
Now, there will be at-most n-1 _'s in the partial products, which means n-1 addition operations. Apart from those, there will be at-least n additions (if there isn't a carry from the addition of the left-most digits in the partial products), and at-most n+1 additions (if there IS a carry from the addition of the left-most digits in the partial products). This makes a total of, at-most, n-1+n+1 or 2n addition operations in this step. So why are they saying 2n2?


texts: Common idea in Karatsuba, Gauss and Strassen multiplication

texts:
The identities used in multiplication algorithms by

Karatsuba (integers)
Gauss (complex numbers)
Strassen (matrices)

seem very closely related. Is there a common abstract framework/generalization?


texts: Is it possible to evaluate $n!$ in $O(1)$?

texts: I'm working on a formula that'll evaluate the partial sum of the harmonic series from $t_1$ to $t_n$. The problem is that I'm almost certain the final formula will include factorials. But if the formula has a factorial, then it's runtime complexity would be at least $O(n)$. And this would defeat the entire point of having a general formula, because I can just iterate over the first $n$ terms and add those in $O(n)$. Utilizing the gamma function wouldn't help either since it'll require $n$ "integration by parts" steps. So is there any way to evaluate factorials faster than $O(n)$?


texts:
What is the big-O notation of the following functions :
$\displaystyle\sum_{i=1}^n \left(\begin{array}{c}
n-1\\
i
\end{array}\right)\\\\
\displaystyle\sum_{i=1}^{n} \sum_{j=1}^{n-i}(3j)\\\\
n^{\textstyle\frac{logloglogn}{logn}}$

If possible I would prefer hints on what I should try doing instead of straightforward solutions.


texts:
Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$.

Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?


texts: Rényi entropy at infinity or min-entropy

texts: I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}_{n}}\left( X \right)=\dfrac{1}{1-n} \log_2 \left( \sum\limits_{i=1}^{N}{p_{i}^{n}} \right)$. It then says that the limit as $n\to \infty $ is $-\log_2 \left( p_1 \right)$. I saw another article that uses the maximum of the ${{p}_{i}}'s$ instead of ${{p}_{1}}$. I think that this works out fairly easily if all of the ${{p}_{i}}'s$ are equal (a uniform distribution). I have no idea how to prove this for anything other than a uniform distribution. Can anyone show me how it's done?


texts:
Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$:
$L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$

The first thing I tried to do is to find a 3CNF formula $\phi$ such that  $\phi \notin L$ and I haven't managed to do so. Is it possible that simply all 3CNF formulas have such an assignment (and so the problem is in $P$) or am I missing something ?


texts:
I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices.  For example if I have a set A = {1,2,3} and a relation R = {(1,1),  (1,2), (2,3), (3,1)}.

What is the resulting Zero One Matrix representation?
How exactly do I come by the result for each position of the matrix? How to tell if it is reflexive, transitive, antisymmetric or symmetric?


texts:
I'm looking for a general reference cataloguing types of automata. Any introductory textbook will cover DFAs, NFAs, PDAs, and TMs, but there are countless more automata of practical or theoretical interest — linear bounded, embedded pushdown, nested stack, tagged finite, and so on. Online resources for these tend to be scattered.

Is there any sort of comprehensive reference, whether online or in print? Even incomplete surveys would be helpful.


texts: Resizing and aliasing in computer science

texts: If you resize an 1000x1000 raster image to 10x10 and resize it back to 1000x1000 is this considered to be an example of aliasing?


texts: Is deciding whether or not a graph is bipartite in $L$?

texts:
Let's consider the problem:

  Prove that decision whether a graph is bipartite is in $LOGSPACE$.

I am convinced that I should use Reingold's theorem. I know that I test whether graph contains an odd-length cycle.

For a given graph $G = (V,E)$ I can define the graph $$G' = (V', E') \\ V' = \{ v^1, v^2 | v \in V \} \\ E' = \{(u^1, w^2), (u^2, w^1) | (u,w) \in E\}$$

And now, the vertex $v$ resides in odd-length cycle iff there is a path between $v^1$ and $v^2$.

But, how can I construct $G'$ using $LOG$ memory?


texts: Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$

texts:
I am currently solving a problem that I have reduced to computing the following function efficiently.

$$T_k(n) =  T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$$

The base cases are $\forall n < k: T_k(n) = 0$ and  $\forall k \leq n < 2k: T_k(n) = 1$ Note: $n$ and $k$ are non-negative integers.

I need to compute this function for multiple values of $k$ and $n$.
I can compute this function in $\theta(n)$ by a simple recursive function using just the definition and speed up the computation by using memoization. However, this isn't fast enough and I was wondering if there is a closed form expression for it and can be computed in $o(n)$.

I have no idea how to solve this recurrence.


texts:
Show that proving 2SAT is not NP-Complete would prove that 3SAT is
  not in P.

Or eqivalently -

  Show that proving 3SAT is in P would prove that 2SAT is NP-Complete.

I can see there is an easy reduction from 2SAT to 3SAT and it seems like it is the key here, but I can't quite prove the statement above. Can anyone help?


texts: Turing's solution to the Entscheidungsproblem

texts:
Based on what I have read so far, to me it sounds like Alan Turing's solution the Entscheidungsproblem means that there is no algorithmic solution to tell whether a given algorithm with input will eventually halt or not. But why is this so crucial in the "computability" world?

It sounds like if I write a program (let's call it P) and have an input, there doesn't exist a separate program that can read in P and the input to tell whether P will halt or not - so what? Can't I just run P to see if it will halt?

I would greatly appreciate it if someone can explain to me what it means to have no algorithm to decide whether a program will halt or not.


texts: What language should this NFA recognise?

texts:
I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise

From my understanding, this NFA accepts strings that contain at least two $1$s, but this is not precise, because, e.g., between the two ones we could have a $0$ or nothing ($\epsilon$). We can also have any number of $0$s or $1$s after these two $1$s.

My guess is that this NFA recognises a language whose strings contain the substrings $11$ or $101$, but I am not sure.

Can you help me defining the language that this NFA recognises?

In general, what is the best way to see what language is recognised by a NFA?


texts:
I took a typical computer architecture class a long time ago as an undergrad and since then I've done a fair amount of low-level systems programming down to the assembly level and worked on OS kernels. However, I still acknowledge that I have some gaps when it comes to understanding how memory subsystems work in multiprocessor and multicore systems.

My question is the following: Is there any good book or other good source covering memory buses and caches on multiprocessor and multicore systems? I'm specifically interested in what exactly happens in hardware when e.g. a processor claims a lock on some memory address. How much background traffic on the memory bus is caused by locks that might slow down unrelated memory intensive code? What kind of lock granularity is typically offered by hardware? What kind of stalls can occur when multiple CPUs try to concurrently write into memory (i.e. not just the same address, but same bank etc.). What kind of issues come up when multiple cores share the same caches? In other words, everything a kernel engineer should know about memory to get rid of hidden bottlenecks.

I know this is a pretty broad question, but I would hope that someone has at least written a book like this. Alternatively, that there's a small set of books that cover all of this.


texts: Why/how does the definition of PCP use randomness?

texts:
I am confused by the definition of probabilistic checkable proofs.

Language $L$ has an $(r(n),q(n))$ - PCP verifier, if there is a PPA V satisfying:

Efficiency: $V$ uses at most $r(n)$ random coins and makes at most $q(n)$ nonadaptive queries to location of $\pi$.

Completeness: $x \in L, \exists \pi \in \{0,1\}^*, Pr[V^{\pi}(x)=1]=1$

Soundness: $x \notin L, \forall \pi \in \{0,1\}^*, Pr[V^{\pi}(x)=1]\leq\frac{1}{2}$

The main question:

Why does PCP need randomness?
How exactly are random coins  used in the PCP?
And what happens when these random coins are actually deterministic?
Where does the effective proof length bound of $2^{r(n)}q(n)$ come from?