texts: How to identify named points by coordinates?

texts:
The problem:
This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (which is the start and the end of the edge). The nodes can be in an arbitrary order, and the whole list can contain duplicates. The wanted output is a list of each node (identified by name) and it's coordinates.

It can be assumed that the input uniquely identifies each point correctly, otherwise the algorithm can cancel with an error.

here is an example:

The input could be (AA,BB,CC are names of nodes)

AA,BB = (1,1),(2,2)
BB,AA = (2,2),(1,1)
BB,AA = (1,1),(2,2)
AA,CC = (1,1),(3,3)

The output would be :

AA = (1,1)
BB = (2,2)
CC = (3,3)

So essentially form a list of undirected edges, I want to fetch the list of named nodes.

My current solution:
is a naive implementation, where I'm simple iterating (or recursing) through the input, I note 2 possible coordinates for each named node. If a coordinate verifies with another line of input I mark it as 'confirmed' and add it to the final result (and remove it from the set of 'possible' coordinates).

What I want:
is a better solution, because this feels like a standard problem of graph theory. Can this be reduced to an existing problem, with an existing algorithm? I guess I'm overthinking this, and I all I need to do is putting the input in some kind of mathematical struct and the the solution is trivial or automatically there. Any ideas? Can this be reduced to a standard-problem? Is it possibly NP hard (so my naive implementation is the best I will find)? I'm also struggling to find a unique identifier, for a better solution. Is a name of a point uniquely identifying the 2D coordinate, or is the 2D coordinate uniquely identifying the named node? I have a bit of a blockage in my thinking and can't find a better way than my current one. I'm implementing it in Python, but if anyone has an idea (or hints) in plain words or pseudocode I'm happy to read them.

Thanks


texts: A* 8-puzzle problem worst case memory usage

texts:
We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem.
We have to answer the following question but I can't figure out what it should be.

Our assignment is derived from this.

  How many board positions are in worst case in memory in function of board size N (where N is the side of a board of size NxN). Give a as low as possible upper bound. You can assume that a board configuration is never in the priority queue several times.

I was thinking about N^2! but that is impossible because not every board position can be reached.


texts: Superpolynomial time set such that SP=NSP is known?

texts:
Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer?

UPDATE: It must be defined by time and strictly between $\mathsf{P}$ and $\mathsf{EXPTIME}$. I was wondering, what if Cobham's thesis is wrong and we are fighting with $\mathsf{P=NP}$ because of that thesis when the really useful question is another one? Maybe one that's even already answered?


texts: How can I download a streaming file without the file's specific address?

texts:
I want to download a streaming file, but I don't know the real address of that file, only the address where the stream is.
How can I download that file? Is it possible to know the address of the file by sniffing the connection?


texts:
While Learning about removing null moves from NFA , I came across a thought....

To Remove Epsilon moves we follow following steps :

Find Closure of all states which have null moves
Mark these states which have null moves
Make a revised transition table without epsilon column and Find all possible transition for those marked states by using their Closures.
you will get nfa without null moves/epsilon moves

Where is the issue : Actually, Doubt arises when you think of an nfa like this :

If we try to remove epsilon moves out of it...

Initial transition Table :

Now finding closure for q0, q1 and q3.

Which is CL(q0) = {q0,q1,q2}
CL(q1) = {q1,q2}
CL(q3) = {q2,q3}
We find a transition table after following above steps which is :

The question gets quite tricky...

because now this nfa has q1,q2 where there is no way to reach them..

So What do you think we will remove q1 and q2 as they are unreachable or we will draw a nfa with them...


texts: Which Grows Faster: Factorial or Double Exponentiation

texts:
Which of the functions among $2^{3^n}$ or $n!$ grows faster?

I know that $n^n$ grows faster than $n!$ and $n!$ grows faster than $c^n$ where $c$ is a constant, but what is it in my case?


texts:
When translating an NFA into an equivalent DFA, we can say that all
  states that contain the final states of NFA, is the final state of
  DFA.

What should my arguments be in order to prove this?


texts:
I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is:

  Prove by induction that if all nodes in a splay tree is accessed in
  sequential order, the resulting tree consists of a chain of left
  children.

When I take a set a set of numbers like 5,1,3,6,2,4 and put them into a Splay tree, and then access them all sequentially (1,2,3,4,5,6), it is very easy to see that the question statement is indeed true (This is a great visualizer) . I just can't find a way to write it in a proof by induction. Any help would be greatly appreciated as I am a struggling beginner.


texts:
I'm trying to study for an exam and having difficulty with the following practice questions. Any help would be appreciated.

Give a language $L$ such that $L$ is not recursive but $\text{prefix}(L)$ is regular.
Give two languages $L_1$ and $L_2$, such that $L_1$ and $L_2$ are not recursive, but $L_1\cap L_2$ is recursive.
Give a language $L$ such that $L$ is regular but $\text{unary}(L)$ is not context-free.


texts: Infinite prefix-closed context-free languages contain an infinite regular subset

texts:
The Problem:

Say that a language is prefix-closed if all prefixes of every string
in the language are also in the language. Let C be an infinite,
prefix-closed, context-free language. Show that C contains an infinite
regular subset.

Can we show this by using Myhill-Nerode Theorem?


texts: Problems that don't have polykernel when parametrized by vertex cover

texts: Are there any problems apart from chromatic number, which is $FPT$ when parametrized by (the size of a minimum) vertex cover, and that does not admit a polykernel when parametrized by (the size of a minimum) vertex cover (under standard complexity assumptions)?


texts: Compressing two integers disregarding order

texts:
Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to represent.

So, if we're given a set {x,y} where x,y are two different 32-bit integers, can we pack them into 63 bits (rather 64)?  It should be possible to recover the original 32 bit integers from the 63 bit result, but without being able to recover their order.


texts: How do I see SSL/TLS packet data in clear?

texts:
Hey all I have a weird question (first time poster so forgive me if this is super newb)...

I am wanting to see the inner workings of a SSL/TLS connection between a client and a server at the packet level (in the clear) in order to learn. Is there a way to do this where I will see all of the traffic including the handshake?

Should I just setup a webserver that uses SSL/TLS and then use ssl strip & tcpdump to grab the packet capture? Will that even work in order to grab the full connection in the clear?

I am not super familiar with the SSL/TLS stack and I would like to do this in order to learn how it works at a lower level.


texts: How to generate unique keys for different two dimensional matrices having different sizes?

texts:
No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it should be placed in this kind of table (as a row) along with its output value. I have taken eight rows , but it can be anything. (eight rows = eight matrices )

My main task is to find key value pair for each row in the table in image (given) for applying hashing. The first column is size of matrix ,second column is matrix elements and the third column is some output value ( getting output values by applying some algorithm , which is not the matter of concern here ). For every row, the first two columns together should uniquely represent a key and the third column should be value . If I get the same key again , I won't compute the value again ; I will just reuse the value .

For example fourth row is a 2*2 matrix . If I get exactly the same matrix again , then I won't compute its output value again. I will directly use that previously calculated output value .

So I wanted to know how to form a key here ? What hash function can I use ? I am doing all these to avoid repeated calculations and to reduce time complexity.


texts: Refutation of pigeonhole using resolution

texts:
I am trying to find a way to refute the pigeonhole formula using resolution.

Lets assume that $x_{ij}$ is true if $i^{th}$ pigeon is in $j^{th}$ hole.

Thus, with $n$ holes and $n+1$ pigeons, the first condition "every pigeon must be in a hole" can be represented as

$$
\alpha_n = \bigwedge_{1\leq i \leq n+1} (x_{i1} \vee \dots \vee x_{in}),
$$

and the second condition "no two pigeons are in same hole" can be represented as

$$
\beta_n = \bigwedge_{1\leq j\leq n} \bigwedge_{1\leq i<k\leq n+1} \neg(x_{ij} \wedge x_{kj}) = \bigwedge_{1\leq j\leq n} \bigwedge_{1\leq i<k\leq n+1} (\neg x_{ij} \vee \neg x_{kj})
$$

The complete piegonhole formula can be represented as $\varphi_n = \alpha_n \wedge \beta_n $.

With $n=1$, it is easy to refute $\varphi_1$ with resolution, as shown below:
$$
\alpha_1 = x_{11}\wedge x_{21} \\
\beta_1 = \neg x_{11}\vee \neg x_{21} \\
\varphi_1 = x_{11}\wedge x_{21} \wedge (\neg x_{11}\vee \neg x_{21}) \xrightarrow{unit-resolution} \sqcup\ (empty\ clause)
$$

However, with $n\geq 2$ there is no unit-clause. For example with $n=2$, we have only 2-clauses. In that case a possible resolution of 2 clauses will produce another 2-clause.

Thus, I am wondering how to produce a refutation proof for $\varphi_{n\geq 2}$ with resolution, as we know that resolution is refutationally complete.

For reference, $\alpha_2$, and $\beta_2$ should look like below:
$$
\alpha_2 = (x_{11} \vee x_{12}) \wedge (x_{21} \vee x_{22}) \wedge (x_{31} \vee x_{32}) \\
\beta_2 = (\neg x_{11} \vee \neg x_{21}) \wedge (\neg x_{11} \vee \neg x_{31}) \wedge (\neg x_{21} \vee \neg x_{31}) \wedge (\neg x_{12} \vee \neg x_{22}) \wedge (\neg x_{12} \vee \neg x_{32}) \wedge (\neg x_{22} \vee \neg x_{32})
$$


texts: Expected number of independent sets of size $k$ in random graph $G(n,p)$

texts:
I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is included with independent probability $p$. I would like to be able to calculate this for arbitrary $p$ if possible.

I have come across the article [1] which provides a formula for the special case $p = 0.5$.

I have also come across the article [2] which in p. 12 provides a value for some cases other than $p = 0.5$, so I would assume it is known for some $p$ values other than $0.5$.

My questions are:

Do you know how one shows, or could you provide a reference for the formula shown in [1] for the case $p = 0.5$. The paper gives some references but they are about clique problems and I am not sure how I could arrive from them to the result shown in that paper.
Is there a known formula for arbitrary $p$?
If not, for what $p$ values is a formula known and where could I find such formulas?

[1] Chromatic and Independence Numbers of $G_{{n}, {{1}\over{2}}}$

[1] Feo, Thomas A., Mauricio GC Resende, and Stuart H. Smith. “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42, no. 5 (1994): 860–78.


texts:
From our computational complexity, there's a question asking to prove 3CLIQUE is decidable.

The definition of 3CLIQUE is:
$$\{(V,E) : G = (V,E)\text{ is an undirected graph that contains a clique of size 3}\}.$$

I know this is an NP problem, and NP is a set of problems that easy to verify but hard to solve, but I don't know how to prove. Is there anyone who can help me on this?


texts: Proving that the sum of DTIME and DSPACE are not equal

texts:
I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$.

There isn't a solution provided in the textbook. I've been working with a solution involving padding but I haven't been able to come up with a solution.

Any tips would be appreciated! Thanks in advance.


texts: How to prove by contradiction that every nonempty hereditary language contains the empty string?

texts:
A language L is called hereditary if it has the following property:

For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L.

Prove by contradiction that every nonempty hereditary language contains the empty string.

Here's my attempt:

To prove by contradiction, we assume that for every nonempty string x in L, there is no character in x which can be deleted from x to give another string in L.

This means that if a character in x is deleted an empty string is left. Since an empty string is also a string, every nonempty hereditary language contains the empty string.

I'm not exactly sure how to proof by contradiction. Can someone help review this?


texts: Determine the number of elements that is divisible by a prime number in an array

texts:
I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers.
For each of the prime numbers, I want to know how many numbers in the first array are divisible by this prime number.
For example:

Array = {5 5 7 10 14 15}
Set = {2 3 5 7 11}
result:2:2; 3:1; 5:4; 7: 2; 11:0

Brute force by using nested loops works, but is there a faster way?


texts: Tendermint Consensus - Resilient up to 1/3 of Byzantine participants

texts:
Tendermint Consensus is resilient for up to 1/3 of Byzantine participants.

Question: What actually happens after when the network hits the threshold of byzantine actors? Forking happens? Does transaction fails for honest nodes?

Similarly, for all the BFT/PBFT consensus algorithm, what happens after when the network hits the threshold for Byzantine actors?


texts: Derivation of implicational propositional axioms

texts:
Is there a way to subtract and add properties of axioms to generate new axioms?

For example:

{L} = {P S K} // natural deduction

{P S K} = {P H K I} // natural deduction

{S K} = {?} // constructive logic

{K I} = {?}

Where:

L = ((A -> B) -> C) -> ((C -> A) -> (D -> A)) // Łukasiewicz's axiom system

P = ((A -> B) -> A) -> A // Piece's Law

H = (A -> B) -> ((B -> C) -> (A -> C)) // Weak hypothetical syllogism

S = (A -> (B -> C)) -> ((A -> B) -> (A -> C))

K = A -> (B -> A)

I = A -> A

I want to be able to be able to add and subtract axioms such that
P + S + K = P + H + K + I implies S encodes the properties of H + I

I'm probably using unjustified assumptions here. For example, I assume you can derive S from H and I, without using P or K. Ideally, there would be a way to automate the process of constructing and destructing axioms (though it'd probably be NP hard).


texts: What kind of language would you suggest for an University compiler project?

texts:
I'm not an instructor. I'm a student doing such course. And I'm just trying to figure out what to do, because we're not given an input language.

What kind of (input) language would you suggest for an University compiler project?

It's a project typical to the compiler course in CS programs.

However, I've been confused about, whether it would be easier to design a language for the project or use some existing programming language.

It should be able to handle the following requirements:

Readable (no binary noodles)
Comments
At least two different types of data (type errors must be captured at the latest during the run)
Integrity technology
Making choices (if tms)
Playback (loops, recursion etc)
Parameterizable subroutines (functions, methods, etc) that can use local variables

Additional features

Tables (multidimensional, 0.5 cr, one-dimensional 0.25 cr)
String input and output (0.25 cr)
String interpolation or printf-style formatting by yourself (0.25 cr)
    Complex printf formats (0.25 cr)
Records and variants (0.5 cr)
Generic (Static) Types (0.5 cr)
Classes and Late Binding (0.5 cr)
First-class functions (0.5 cr)
Garbage collection (entirely self-made) (1 cr)
Recursive pattern match (garden Haskell) (0.5 cr)
Lazy calculation (1-2 cr depending on the implementation technique)

Additionally the implementation would include:

Relatively effective interpreter without separate intermediate language 0 cr
Generation of intermediate language (eg own, JVM or LLVM) 1 cr
Generation of a machine language (eg AMD64 or ARM) from its own intermediate language
Naive register allocation 1 cr
Smart register allocation (eg graphing) 2 cr

Also, what existing programming languages would fit into all of these? Does it have to be a functional language or does even C implement all of these?


texts: Range sum query - tree representation efficiency

texts:
I was reading about possible solutions to the well known problem:

Given array A with length N create a structure that enables

Answering what is the sum $\sum_{k=i}^{j} A[k]$
Updating $A[k]$

I've seen most solutions use binary index tree but was curios whether it's possible to just use a regular tree that is built using similar qualities.
So given $A = [5, 4, 7, 9, 1]$
I try to construct a tree by creating a tree node for each value that has a start and end (which are just the index in the beginning.
To construct the tree I push all the starting node into a queue $Q$
while not Q.empty():
  next <- []
  for i in range(Q.size()):
    f <- Q.front()
    Q.pop()
    if Q.empty():
      if marker:
        parent <- make_parent(f, marker)
        next.push(parent)
      else:
        marker <- f
    else:
      f2 <- Q.front()
      Q.pop()
      parent <- make_parent(f, marker)
      next.push(parent)

  for n in next:
     Q.push(n)

After the this ends marker will hold the root

(I have working c++ code but I tried to provide something more abstract and simple)
and to get a sum of range I perform the following (assuming I have an array Nodes that holds all the leaves) and that the query starts with the root of the tree that we created above
sumRangeNode(int i, int j, Node* n)
  if i == j
    return Nodes[i]
  if n == null
    return 0
  if j < n->start || i > n->end
    return 0;

  if i <= n->start && j >= n->end
    return n->val

  return sumRangeNode(i, j, n->left) + sumRangeNode(i, j, n->right)

The question is does it still have the $\log(N)$ complexity, I've tried to reason about it but struggled with:

The fact that I might be building a tree with "stragglers" like the $1$ in the example
The fact that I recursively explore right and left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.


texts:
Having the grammar G = (V,P,S) with variable V = {S,A} over the alphabet {a,b} with the rules:

S->aA
A->Sbb|b

How can i recognize which kind of grammar is this? I think that's not "regular expression" because in the second rule there are 2 letters (bb) instead of one, so i think it's a "context free" grammar. Am i right?


texts:
How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?

A general resource graph which can be completely reduced and hence is free from deadlock is shown below.

As depicted above, R1 and R2 are resources and P1 and P2 are processes.


texts: Compute the edit distance between two words in which substitution is not allowed

texts:
How do I compute the edit distance between two words in which substitution is not allowed?
The allowed operations include insertion (with cost 1) and deletion (with cost 1), but not substitution.
How is this supposed to be computed without substitution?


texts: Can epsilon be in the input alphabet of an FST?

texts: Can epsilon be in the input alphabet of an FST ?


texts: Is spectral radius of a graph related to its radius?

texts: I am searching for algorithms to estimate the radius of a graph, and I found out that there are papers about the spectral radius of a graph. As far as I know, the radius of a graph is $\min_{v \in V} ecc(v)$ where $ecc(v)$ is the depth of a tree rooted at $v$, and the spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Are these two concepts related in some way?


texts:
Given a set S of integers, the task is to partition the set into subsets such that:

Total number of partitions is maximized
Each partition has sum at least K

This looks like a variant of bin-packing problem, in which the bin has to filled upto a minimum capacity and the objective is to maximize the number of bins. I looked up the solutions of bin-packing problem, turned out ffd was the best approximation solution to it.

Could someone please tell me how to approach the partition problem?


texts: How do we sort the chunk in the first pass of external merge sort?

texts:
Referring to the 9th page of a slide, when we use multi-pass multi-way external merge sort on a file with $N$ pages using $B$ buffer pages, in "pass 0" we'll read a chunk of $B$ pages into all buffers, sort the chunk, and write it back to disk, repeatedly to produce $\lceil{N/B}\rceil$ sorted chunks. In later passes, we'll use $(B-1)$ buffers for input and the last buffer for output to merge $(B-1)$ sorted chunks together each time each pass.
As is not mentioned at all, how the whole chunk (in pass 0) can be sorted when all buffers are being used for input?


texts: How do I approach this algorithms problem?

texts:
I'm preparing for the next hashcode by solving the following prev. problem:

Given a pizza of size R x C with cells containing either mushrooms or tomatoes as shown bellow:

We are given 2 parameters: L and H. The goal is to split the pizza into rectangular slices such that each rectangle contains at least L cells of mushrooms and at least L of tomatoes. Furthermore, each split rectangle should contain at most H cells in total. Note that not all of the pizza needs to be contained in the split. The goal is to maximize the number of cells

So in the example above, L=1 and H=6 so in this case The ideal split will be:

So each split contains at least 1 mushroom and at least 1 tomato, and each split contains at most 6 cells. I am not sure how to approach the solution to this problem? Which topics should I read about to understand how to solve such a problem?

P.S. I'm not sure what tags to add for this problem but I will add the appropriate tags and title once I receive guidance.


texts: Reference for Elliptical Basis Function Neural Networks

texts:
I found the following assertion in a neural networks FAQ:

  Radial networks typically have only one hidden layer, but it can be
  useful to include a linear layer for dimensionality reduction or
  oblique rotation before the RBF layer

But I could not find any "formal" reference (published works) showing it. I found some papers describing EBFNN's, but they implement full covariance matrices on the RBF units. I could not find anything about this approach with an extra linear layer before the RBF layer. The theory is ok for me, it makes sense and works. What I need is any published work with this information. Is there one?


texts: Can Reduction for Undecidability/Decidability Problems Go Both Ways?

texts:
This Problem sparked my question:
Does a TM $M$ enter state $q$ on input $w$?

I proved it was undecidable in this format using the Halting Problem as a subroutine:

If HALT
    simulate M on w and return result
 else
    return false

Since HALT is undecidable, this given problem is undecidable as well.

However, the given solution proved in the opposite way, by creating a decider for the problem, and using it as a subroutine to solve the Halting Problem.

Is my direction of the proof still valid, and can my approach be used to prove other undecidable problems (using a known undecidable problem as a subroutine rather than the other direction)?


texts: Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

texts:
I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly $10\sqrt{n}$ strongly connected components is in $NL$.

We saw in class that checking whether a directed graph contains exactly $C$ strongly connected components is in $NL$ for any fixed $C$, but I thought about this question the whole day and I absolutely have no idea how to do it in $NL$ when then number of SCC required is $10\sqrt{n}$. In the test this question was worth 20 points, so it shouldn't be too hard so I thought that maybe I am missing something important.


texts:
Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial
Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that solves travelling salesman needs super-polynomially many constraints.

Suppose $P=NP$ by 'some' method then we can solve the optimal tour explicitly and trivially setup a LP that 'solves' the TSP problem. So $P=NP$ implies that TSP has a poly-size LP formulation. The contrapositive is that TSP has no poly-size LP formulation implies $P\neq NP$. This paper shows TSP needs super-polynomially many constraints.

So why doesn't this show that $P\neq NP$?


texts:
I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis:

s = <string matching regex R1>
t = s.replace(<regex R2>, <string matching regex R3>)
# What is the set of possible strings of t?

More formally, given DFAs $R_1$, $R_2$, and $R_3$, I want to find some automaton $R_o$ that is the result of replacing substrings of $R_1$ that are accepted by $R_2$ by some string that is accepted by $R_3$.

Unfortunately, while the literature seems to discuss this, I am unable to pin down a precise implementation of this operation. In addition, I am having trouble even defining the set of strings that $R_o$ should accept. Does there exist an algorithm to solve this problem? Is it even solvable in general?


texts: Why is reduction mostly associated with proving hardness?

texts:
Reduction is a powerful problem solving technique that is helpful in solving problems in terms of the solution to other problems, it can also be used for complexity analysis. Why does most of the literature restrict mentioning reduction to proving hardness which seems to be a pessimistic point of view for reduction (unless P=NP ofcourse :) )?

EDIT: Just to make sure my question is well understood. I am aware that reduction is used for problem solving and designing or analyzing algorithms, I have solved hundreds of contest problems with reduction which leads to my question of why is a random search for reduction lead to the NP completeness context with book chapters and papers illustrating its power from the complexity theory point of view when the same basic definition for reduction can be used for designing algorithms but just rarely (or implicitly) mentioned. In other words, why does a random sampling of the occurrences of the term "reduction" show a clear bias towards its use in complexity theory.


texts: Name for concept: each pair of sets is either nested or disjoint

texts:
Does this property have a name?

  Given a collection of sets $\mathcal{P}$, for   all pairs $A, B\in\mathcal{P}$, either $A\cap B=\emptyset$ or $A\subseteq B$ or $B\subseteq A$.

This concept could equally apply to monoids, groups, partial orders or other mathematical structures, with some adjustments to the definitions. For instance, for monoids and groups we would replace $A\cap B=\emptyset$ by $A\cap B=\{\epsilon\}$, where $\epsilon$ is the unit of the monoid/group.


texts: is it possible to know if a language is regular if its equivalence classes are finite?

texts:
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.

1)suppose we have some language L over $\Sigma$, can we know if L is regular if all of it equivalence classes of relation $R_L$ is finite?

2)and what about L*? is it finite? i mean the cardinality is infinity(alef), but can it be made into a finite language?

Edit: my question is about Myhill–Nerode relation

i am curious about those and your input would really help me understand more about it

thank you very much!


texts:
Definition
  A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log
  space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/Boolean_circuit#Uniform_Boolean_Circuits)

Can anyone exlain this? I know what boolean circuits are, so only explanation needed is what  and transducer exactly are.


texts: Questions on Sipser's NP implying verifiability?

texts:
I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up along with to check if I'm understanding.

For the forward implication (there exists a verifier $V$ and we want to show this implies the existence of an NTM $N$), we can, according to Sipser, "Nondeterministically select string $c$ of length at most $n^k$. Then we run $V$ on input $(w,c)$ and accept if $V$ accepts, otherwise reject." I'm wondering if $V$ would be run as part of the algorithm on each branch of $N$. In other words, for any node in the computation tree of $N$, the verifier will be run on the that current string, and the branch will produce a YES answer only if the verifier accepts that string. Am I understanding this correctly? So it would run concurrently, and since the verifier runs in $O(n^k)$ and the NTM runs in $O(n^q)$, then this still runs in polynomial time if the verifier is run at every step in the computation.
For the backward implication, we assume $A$ is decided by a polynomial time NTM and construct a polynomial time verifier $V$. When we say that $A$ "is decided by" $N$, does this mean that $N$ is correctly able to determine if any given branch of computation results in accept or reject? This feels a bit cyclic to me, since we are trying to construct the verifier $V$ given $N$. I don't see how $N$ could decide $A$ without $N$ having a verifier constructed already. In other words, without a verifier, how would the NTM know if it should accept/reject on any of its given branches?


texts: Feature detector that doesn't use corners

texts:
I'm trying to use computer vision to identify objects an image. I am currently using the SURF algorithm, but Harris and SURF both find virtually no points on our objects (a paper ball and a deodorant can) due to their simple features. If it does find points it finds one or two that aren't the same points it find in the new frame. SURF also finds a large amount of points on our floor due to the contrast of the black dots on the carpet.  Here's a sample image:

Is there a feature detector that doesn't use corner detection/curvature?


texts: Is the ratio between a bloom filter intersection and a bloom filter union equal to that of their original sets?

texts: Given two sets, S1 and S2, and their corresponding bloom filters, BF1 and BF2, is there a way to prove that |BF1 ∩ BF2|/|BF1 ∪ BF2| = |S1 ∩ S2|/|S1 ∪ S2| (we can assume both bloom filters are generated using the same set of hash functions)? If not, is there a way to approximate one given the other?


texts: Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

texts:
CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have
MAYBE-MST-C(G,w)
  T = empty set
  for each edge e in G, taken in arbitrary order
    T = T U {e}
    if T has a cycle c
      let e' be a maximum-weight edge on c
      T = T - {e'}
  return T

I've found several other solutions (here, here and here) that claim that this procedure succeeds in finding an MST. However, I don't understand any of their proofs.
I can see that this results in a spanning tree. It's spanning because adding every edge e would certainly span G, and removing parts of cycles e' certainly doesn't affect that. It's a tree because any cycle that is added is guaranteed to be immediately removed.
I'm having a hard time seeing why it's minimal (or perhaps it actually isn't?). One of the solutions uses the result of exercise 23.1-5:

if $G$ and has some cycle $c$, then
there exists some MST of G that does not include the edge $e'$ with the
largest weight on that cycle $c$.

While this result superficially resembles the operation performed in MAYBE-MST-C, upon closer inspection, it's not so obvious that it helps, since in the algorithm, T is not guaranteed to span G until the very end, and also the exercise result only claims that an MST exists when omitting one e'; it doesn't say we need to remove all e'. What if the MST that the exercise guarantees requires us to remove the first e', but keep the second? Further, upon removing e', how are we sure that the edges needed to compete the MST have not been removed in previous iterations of the loop?


texts:
I read that pumping lemma is sufficient condition to prove non regularity of languages but not necessary condition.

I know the first part that it is sufficient is true but not able to understand why is it not necessary. Can someone please help me with this statement?


texts: Best design of a software controlled page table: to echo the TLB?

texts:
I am building some simple system software for the Microblaze FPGA (actually being run on OVPsim at least for now).

The system is to experiment with various memory management regimes.

The first system I want needs to have a very simple paging mechanism and so I want to build a software controlled (only option on a Microblaze) page table.

Is the easiest option just to echo the TLB hardware design - this might waste a few bits but given there are no special circuits optimising this, the simplicity of matching TLB entries to the page table seems like a pretty good choice to me. Is there any reason why I shouldn't do that?

Are there other designs for software controlled page tables that I should look at? (Any papers etc?)


texts: How can I combine my interests for pure mathematics and computer science in college?

texts:
I’m a high school senior who's gone through quite the self-introspection the past few months while applying for college, and I have a bit of a dilemma. All my life, I've loved & excelled at mathematics, and wants to study & explore it very much in depth in college. I get very excited when I read up on fields such as number theory, analysis, topology, and algebraic geometry. On top of that, I've also realized that although I have no experience programming, there are wonderful merits to applying math to computer science and would love to apply my math skills to a fast-growing industry.

I feel, however, that studying comp sci will "limit" the scope and depth of the math I study, because joint programs of math and comp sci will only make you take math classes relevant to the study of computer science. Out of the Common App colleges I'm applying to, Emory, NYU, and BU have joint majors in math and computer science, while UMiami only has a BS in mathematics, and Georgia Tech has BSs in discrete and applied mathematics. For Emory, for instance, I'll be "missing out" on multivariable calculus, complex variables, real analysis, and abstract algebra.

If there is a way to combine these two interests without limiting the mathematics I learn, that'd be amazing, but if not, so be it. If you feel I have certain misconceptions, please feel free to point them out. Lastly, I know this is not the best place to ask this question, as it is directed towards students and researchers of computer science, but I would love your input and appreciate it ahead of time!

Thank you!


texts: Language of all even-length words with no 1's in left half

texts:
Consider the following language:
$$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\},$$
where $\Sigma_1 = \{0,1\}$.
I need to show that this is not regular. I tried to prove this with the pumping lemma.
Imagine that there exists a pumping length $d$, and consider the string $s=0^d1^d$. If we choose $s=xyz$ arbitrarily with $|y| > 0$, we will have three options.

$y$ can be in the first half of the string.

$y$ can be in the second half of the string.

$y$ can contain the first and second half of the string.

In the last option, $y$ can only be in the following form: $0(0)^+$ or $(0)^+(1)^+$. (Here $^+$ means Kleene plus.)
For the last form ($(0)^+(1)^+$), we see that $xyyz$ will have a $1$ in the first half, which is not in $L$.
Consequently, $L$ cannot be regular.


texts: Use of existential quantifier in tuple relational calculus

texts:
It is somewhat confusing to me when to use quantifiers in tuple relational calculus (TRC). I stumbled upon following problem and I am still scratching my head thinking why not TRC query can be constructed without using existential quantifier.

The given problem reads like this:

  Relations:
  student (rollNo, name, degree, year, sex, deptNo, advisor)
  department (deptId, name, hod, phone)
  professor (empId, name, sex, startYear, deptNo, phone)
  course (courseId, cname, credits, deptNo)
  enrollment (rollNo, courseId, sem, year, grade)
  teaching (empId, courseId, sem, year, classRoom)
  preRequisite(preReqCourse, courseID)

  Question: Obtain the names of courses enrolled by student named "Roger".

  Given solution:

{ c.name | course(c) ^
                   (∃s) (∃e) ( student(s) ^
                                     enrollment(e) ^
                                     s.name = “Roger” ^
                                     s.rollNo= e.rollNo ^
                                     c.courseId = e.courseId}

Why I cant just have following? :

{c.name | course(c) ^
                 enrollment(e) ^
                 student(s) ^
                 c.courseId = e.courseId ^
                 e.rollNo = s.rollNo ^
                 s.name = "Roger" }


texts:
Suppose I have a 2D array M[n][n] of integers (in fact, binary is fine, but I doubt it matters). I am interested in repeated queries of the form: given a coordinate pair $k,l$, what is
$$
\sum_{i = 0}^{k-1} \sum_{j = 0}^{l-1} M[i][j]?
$$
Of course, all these values can be computed in $\mathcal O(n^2)$ time total, and after that queries take $\mathcal O(1)$. However, my array is mutable, and each time I change a value, the obvious solution requires a $\mathcal O(n^2)$ update.

We can create a quad tree over M; the preprocessing takes $\mathcal O(n^2\log(n))$, and this allows us to do queries in $\mathcal O(n\log(n))$, and updates in $\mathcal O(\log(n))$.

My question is:

  Can we improve significantly on the queries without sacrificing too much on the updates?

I am especially interested in getting both the update and query operations sub-linear, and in particular getting them both to $\mathcal O(n^\epsilon)$.

Edit: for some more information, although I think the problem is interesting even without this further restriction, I expect to do roughly $\mathcal O(n^3)$ queries, and about $\mathcal O(n^2)$ updates. The ideal goal is to get the full runtime down to about $\mathcal O(n^{3+\epsilon})$. Thus, a situation where an update takes $\mathcal O(n \log(n))$ while a query takes $\mathcal O(\log(n))$ would also be interesting to me.


texts:
Can we infer from the fact that the number of independent sets in product of $5$-cycle two times is $5$ and in product of $5$-cycle four times is $25$, that the capacity of pentagon is $\sqrt{5}$? That is does $\alpha(C_5 \boxtimes C_5)=5$ and $\alpha(C_5 \boxtimes C_5\boxtimes C_5 \boxtimes C_5)=25$ imply $\theta(C_5)=\sqrt{5}$? Why? Or why not then?

Here $C_5$ is pengtagon, $\alpha(G)$ is independence number of graph $G$, $\boxtimes$ is strong product and $\theta(G)$  is Shannon capacity of graph $G$.


texts: What's the difference between declarative syntax and encapsulation?

texts:
I had been first introduced to the idea of declarative syntax when using Angular JS. From what I understand, the idea is that you say, "do this" instead of "in order to do this, do this, this and this". You don't care how it's done, you just want it done, and you pass it off to some lower level of abstraction to do.

Now I'm going over the idea of encapsulation as I learn Java, and the idea seems very similar. From what I understand, the idea is that you break things up into modules, and you define an outwards-facing API for people to use. So people could use your in a declarative manner to say, "do this".

Is this true? If so, what is the real difference between declarative syntax and encapsulation? Just that one describes syntax and the other describes the more abstract design philosophy?

Edit: I think that my question boils down to: what's the difference between making a declarative statement and making an API call?


texts: Why do many developers continue to rely on pseudo-random number generators?

texts: Although hardware based “true” random number generators are available, software-based pseudo-random number generators still remain the predominant method for generating random numbers in use today. Why do developers continue to rely on pseudo-random number generators?


texts: How to prove Exact cover problem is NP Complete using Vertex Cover problem?

texts: Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from Vertex Cover.


texts: Master theorem with $T(n) = 6T(n/10) + \lg^2 n$

texts:
So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here's what i have so far

$$\lim_{n \rightarrow \infty} \frac{d(\lg^2 n)}{d(n^{\lg_{10}6})} = \frac{2 \lg n (\frac{1}{n})}{(\lg_{10}6) n ^{(\lg_{10}6) - 1}}$$

Is there some better way I can think about proving case 1?


texts: Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

texts:
The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem

For instance, the Arora-Barak book explains the theorem using $g(n) = n$ and $G(n) = n^{1.5}$ - but, I can see that $n \in o(n^{1.5})$ as well! So, I'm trying to better understand what "extra" time is guaranteed by specifying that in order for $\text{NTIME}(g(n))$ to be a proper subset of $\text{NTIME}(G(n))$, $g(n + 1) = o(G(n))$, not $g(n) = o(G(n))$...


texts: Why is deleting from a hashtable when there is a linked list at h O(1)?

texts:
I am currently studying hashtables and whilst the concept of chaining makes perfect sense, as does why searching is O(n) and also inserting (at head) is O(1), I dont understand why deleting an item is also O(1), hopefully someone can help me understand.
I am referring to text such as this:

In the worst-case scenario, all of the keys hash to the same array slot, so Search takes O(n),
while Insert and Delete still take O(1).

The reason I don't understand is that if in the example above, all keys hash to the same slot, adding a new item that also hashes to the same slot and is inserted at head is O(1), equally searching for an item is O(n) as it could be the last item in the linked list, to me it seems that deleting an item should also be O(n) as when the value is hashed it leads to the linked list but the list still needs to be searched to find the value to delete?
Any help appreciated!


texts: Why is shared register's consensus number 1?

texts:
I'm trying to understand the consensus number concept. It is trivially clear that a shared register doesn't create any problem when there is only one thread using it. By why does its consensus number isn't more than 1? To me, any number of threads can access and modify the register in a concurrent manner and get the correct value for the time it has been retrieved.
Thank you for your help.


texts: Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

texts:
tl;dr? See last paragraph.

If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form

$ x_{k+1} = \frac{x_k\Big[A\left(n+1\right) + x_k^n\left(n-1\right) \Big] }{A\left(n-1\right) + x_k^n\left(n+1\right)} $

to evaluate $\lfloor x^{1/n}\rfloor$ with $x,n \in \mathbb{N}$, $x \gg 1$ and $n > 2$ it seems (empirical tests only!) to work. Slowly.

As is the case with all of these methods: the closer the initial value $x_0$ to the actual root, the smaller the amount of iterations needed. Many papers have been written about it, although not many for the integer versions, but a simple refinement can be implemented by observing that the root lies between $2^{\lfloor \lfloor\log_2 x \rfloor / n \rfloor + 1}$ and $2^{\lfloor \lfloor\log_2 x \rfloor / n \rfloor}$ so a simpel arithmetic average of these limits should give a significant decrease in the number of iterations needed and, lo! and behold, it does. Small problem: the algorithm is unstable with that seed. Visible in the following pretty picture with a highly abused y-axis (#iterations, bitsize of root, and absolute error) and the index along the x-axis. The radicand used was $5987^{797}$.

The range of indices where the error occurs is outside the range where I would use Halley's recurrence and change to bisection. The cut-off point I have choosen is the intersection between the bisection which is linear $ax^{-1}$ and the approximately linear part of the Halley iterations at the beginning $bx$ which puts the intersection at $\sqrt{a/b}$. Some runs with up to $3\,321\,960$ bits (ca. one million decimal digits) showed $\Big\lfloor\sqrt{A_b\left(\left\lfloor\log_2\left(\left\lfloor\log_2 \left(A_b\right) \right\rfloor\right) \right\rfloor + 1\right)}\Big\rfloor$  with $A_b = \left\lfloor\log_2 \left(A\right) \right\rfloor$ to be a good estimate for the big-integer library in use.

Hence my question: is Halley's recurrence, implemented as described above, numerically stable in the range $(3,\Big\lfloor\sqrt{A_b\left(\left\lfloor\log_2\left(\left\lfloor\log_2 \left(A_b\right) \right\rfloor\right) \right\rfloor + 1\right)}\Big\rfloor)$ with the initial value the arithmetic average of $2^{\lfloor \lfloor\log_2 x \rfloor / n \rfloor + 1}$ and $2^{\lfloor \lfloor\log_2 x \rfloor / n \rfloor}$ or not and, much more interesting, why?


texts: Finding the Big-O and Big-Omega bounds of a program

texts:
I am asked to select the bounding Big-O and Big-Omega functions of the following program:
void recursiveFunction(int n) {
    if (n < 2) {
        return;
    }

    recursiveFunction(n - 1);
    recursiveFunction(n - 2);
}

From my understanding, this is a Fibonacci sequence, and according to this article here, https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/, the tight upper bound is $1.6180^n$. Thus, I chose all the Big-O bounds >= exp(n) and all the Big-Omega bounds <= exp(n). Below are the choices:
O(1)
O(log n)
O(n)
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))

The answer choices I selected:
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))

However, it was alerted that a few of my answers were incorrect (not sure which of them). This seems strange, considering that this recursive function mimics the calls of a fibonacci sequence which has a Big-Theta exponential time complexity.


texts: Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?

texts:
Karlheinz Brandenburg depicts a MP3 encoder like this:

Source: MP3 and AAC Explained

I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the psychoacoustic model be applyed to the so called lines after the modified discrete cosine transform (MDCT) without performing a FFT?

I have some literature here, saying the frequency resolution is not accurate enough. Does this mean, dividing the original signal into 576 lines (like the filterbank and the MDCT do) is not accurate enough for the psychoacoustic model to work properly? Is the FFT more accurate?


texts: How Cellular Automata is related to Automata Theory?

texts:
I have read about Automata Theory where it is about the study of abstract machines and automata.

And i know that an abstract machine takes the input, process it and create the output, just like Conway's Game of life.

But, what a formal defination can relate it to Cellular Automata, what about Elementary Cellular Automata, can it related also?


texts: Particular techniques for NP-complete problems

texts: Is it possible to show particular classes of techniques (for instance dynamic programming) cannot produce polynomial time algorithms to any NP-complete problem?


texts:
This problem takes place on a coordinate plane. I need assistance in creating the algorithm to solve this problem. I am solving this problem in java if you are interested.
I have 1 carpet and 2 tarps.
The 1 tarp covers the carpet (note in some scenarios it may not cover it at all).
The second tarp will cover the remaining area of the carpet, however, this is where it gets tricky. The tarp cannot be a special shape or tilted, meaning the tarp HAS to be rectangular. I am given the inputs of the lower left and top right corners of both the 1st tarp and the carpet. As of now, I have calculated the visible area of the carpet after the first tarp has been placed, the overlapping (non-visible) area of the tarp, and the areas of both the carpet and 1st tarp.
So basically what I am saying is, given a rectangle C (the carpet) that intersects the rectangle T1 (tarp 1), find another rectangle T2T2 (tarp 2) such that the area of T2T2 is minimal.
Below is a picture of some test cases I drew up:

*Excuse my messy handwriting

Cutting to the chase, what I need is help with is developing an algorithm that would satisfy all of the above test cases, given the lower left and top right coordinates of both the first tarp and carpet. Note I am going to be writing this in Java and I currently have an area function and visible area of the carpet function.

Sorry if I was a little unclear on what I am asking, leave a comment and I'll be happy to clarify.
 Note: this is not a homework problem, as many of you may think. This is merely an interesting scenario of another programming problem I had.


texts: Is "represents" a symmetric relation in the provided answer to TAOCP exercise 1.1.9?

texts:
In exercise 1.1.9 of volume 1 of The Art of Computer Programming, the reader is asked to

  formulate a set-theoretic definition for the concept "$C_2$ is a representation of $C_1$"

where $C_1$ and $C_2$ are computational methods described in the previous few pages (reproduced here so the question can be answered without needing the book).

  Let us formally define a computational method to be a quadruple $(Q,I,\Omega,f)$, in which $Q$ is a set containing subsets $I$ and $Ω$, and $f$ is a function from $Q$ into itself. [...] The four quantities $Q$, $I$, $\Omega$, $f$ are intended to represent repectively the state of the computation, the input, the output, and the computational rule.

When I looked at the answer in the back, this definition was proposed:

  For example we can say $C_2$ represents $C_1$ if there is a function $g$ from $I_1$ into $I_2$, a function $h$ from $Q_2$ into $Q_1$, and a function $j$ from $Q_2$ into the positive integers, satisfying the following conditions:

  a) If $x$ is in $I_1$ then $h(g(x)) = x$
  b) If $q$ is in $Q_2$ then $f_1(h(q)) = h(f_2^{[j(q)]}(q))$, where $f_2^{[j(q)]}$ means that the function $f_2$ is to be iterated $j(q)$ times.
  c) If $q$ is in $Q_2$ then $h(q)$ is in $\Omega_1$ if and only if $q$ is in $\Omega_2$

Later on, discussing this definition, Knuth writes (emphasis mine):

  The relation "$C_2$ represents $C_1$" generates an equivalence relation in which two computational methods apparently are equivalent if and only if they compute isomorphic functions of their inputs ...

To be an equivalence relation, a relation must be symmetric. That is, for a relation $R$, $(a, b) \in R$ implies $(b, a) \in R$. I don't believe this is true of the given definition.

Consider the computational methods $C_1$ and $C_2$, where

\begin{align*}
C_2 &= \{Q_2, I_2, \Omega_2, f_2\}\\
C_1 &= \{Q_1, I_1, \Omega_1, f_1\}\\\\
I_2 &= \{a_1, a_2\}\\
\Omega_2 &= \{b_1, b_2\}\\
Q_2 &= I_2 \cup \Omega_2\\
f_2 &= \{(a_1, b_1), (a_2, b_2), (b_1, b_1), (b_2, b_2)\}\\\\
I_1 &= \{c\}\\
\Omega_1 &= \{d\}\\
Q_1 &= I_1 \cup \Omega_1\\
f_1 &= \{(c, d), (d, d)\}
\end{align*}

It can be shown that $C_2$ represents $C_1$ by $g(q) = a_1$, $h = \{(a_1, c), (a_2, c), (b_1, d), (b_2, d)\}$, and $j(q) = 1$.

However, $C_1$ cannot represent $C_2$, because for any proposed $g: I_2
\rightarrow I_1$ it must be the case that $g(a_1) = g(a_2) = c$. But $h(c)$ can
only be either $a_1$ or $a_2$. If $h(c) = a_1$, then $h(g(a_2)) = a_1 \neq a_2$,
but if $h(c) = a_2$, then $h(g(a_1)) = a_2 \neq a_1$. So in either case,
the first requirement cannot be satisfied.

Has this been discussed elsewhere? So far my online searches haven't revealed any answers on the subject. To the best of my knowledge, this hasn't been errata'd (checked here).

Am I understanding the definition properly?

I'm uncertain about my result because of the specific wording "from $Q_2$ into
$Q_1$", which seems to have varying meanings depending on where you ask (if it means "injection", it adds different inconsistencies). It also
seems strange to me that this property would be overlooked, since Knuth also
specifically mentions that "represents" is transitive, and a counterexample like
this is quite easily constructed.

In summary: is it not symmetric? Has this been addressed somewhere? Am I owed 0x$1.00?


texts: How to understand these exposure algorithm rules for System F sub?

texts:
The book "Types and Programming Languages" said System F sub type checking introduce exposure typing rules alongside algorithmic typing and sub-typing rules.

       exposure algorithm

       X<:T ∈ Γ        Γ |- T ⇑ T'
       --------------------------- (XA-PROMOTE)
               Γ |- X ⇑ T'

        T is not a type variable
       --------------------------- (XA-other)
               Γ |- T ⇑ T

The first one seems simple, but the second rule seems bit wrong to me.
"T is not a type variable", which "T" it is referring to?

Does "Γ |- T ⇑ T" mean left and right hand side of "⇑" are same types?

For example, with the type checking

          " Γ |- sone: SPos"

where

          sone= λ A <: Top.
                 λ B <: A.
                  λ C <: A.
                   λ m : A->B.
                    λ n : C. m n.

          and

          SPos= All A <: Top. All B<: A. All C<: A. (A-> B) -> (C-> A).

After applying "TA_TABS" and "TA_ABS" rules

 {A <: Top, B<: A, C<: A, m : A->B, n : C } |- m n :B
-----------------------------------------------------------TA-APP
 {...} |- :- m:T1   ,  {...}|-T1 ⇑ (T11->B)  ,  {...}|-n:T2  , {...}|-T2<:T11

 {...}|-n:T2    we know  T2=C
 then
 {...}|-C<:T11  we get T11=top

 then put it in place

 {...} |- :- m:T1   , {...}|-T1 ⇑ (top->B)
 ------------------------------------------

which rule applies now?

I believe from

{...}|-T1 ⇑ (top->B)

we should get "T1=A->B" , but how?

both (XA-PROMOTE) and (XA-other) seems cannot be applied.

please help!


texts: Is it true that if L* is recursive, L is also recursive?

texts:
Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive?
I know that the opposite direction is true:

If $L$ is recursive, then $L^*$ is recursive.

But I don't know how to prove it in this direction.


texts: What is regular about regular languages?

texts:
I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. However, I'm confused why such language (set of strings) is called regular.

what is regular about regular language?
Is there any relation between regular set in automata theory and regular set in mathematics?


texts:
Given complex number $C=a+ib$, I want to find two complex numbers $C_1=x+iy$ and $C_2=z+iw$ such that $C=C_1*C_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as Integer factoring. Prime complex number has one as its only factor.

Does this problem reduce to integer factoring? Is it NP-hard?


texts: How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

texts:
Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example.

What I am trying to achieve with one sentence

How can I answer the following question by using constraint programming:

  The Euclidean distances between a point $p_4$ and points $p_1(0,0)$, $p_2(0,5)$ and $p_3(5,0)$ are $5.00$, $3.16$ and $4.47$ respectively. Where is $p_4$ on the $xy$-plane?

without using quadratic constraints?

Very short version of the question

There are five points placed on a 2D plane.

We only know the pairwise distance between these points.

\begin{matrix}
d_{12} &= 5.00\\
d_{13} &= 5.00\\
d_{14} &= 5.00\\
d_{15} &= 5.00\\
d_{23} &= 7.71\\
d_{24} &= 3.16\\
d_{25} &= 4.47\\
d_{34} &= 4.47\\
d_{35} &= 3.16\\
d_{45} &= 1.41\\
\end{matrix}

In addition, we know the coordinates of first three points.

\begin{matrix}
p_1 &= &(0,0)\\
p_2 &= &(0,5)\\
p_3 &= &(5,0)\\
\end{matrix}

And we want to find the coordinates of remaining two:

\begin{matrix}
p_4 &= &(3,4)\\
p_5 &= &(4,3)\\
\end{matrix}

How can I formulate this problem without using quadratic constraints? Note that in order to impose the Euclidean distance between two points, we need to use square of differences.

Detailed version of the question

I am trying to formulate the graph embedding problem as constraint satisfaction problem.

Graph embedding is simply assigning coordinates to the vertices of a graph by considering edge weights, where the weight $w_{ij}$ of an edge $\{i,j\}$ determines the Euclidean distance between the nodes $i$ and $j$.

My decision variables are two arrays, $X$ and $Y$.
$X_i$ and $Y_i$ are the $x$ and $y$ coordinates of node $i$.

The mathematical model can be written as:

given: $G = (V,E)$

decision variables: $X = \{x_1, \dots, x_{|V|}\}$; $Y = \{y_1, \dots, y_{|V|}\}$

subject to: $\forall \{i,j\} \in E$; $(x_i-x_j)^2 + (y_i-y_j)^2 = w_{ij}^2$

As discussed here,

  $(x_i-x_j)^2 + (y_i-y_j)^2 = w_{ij}^2$

is a non-convex constraint.
Is there any way to formulate this problem using convex constraints?

I came up with something:

Assuming that the coordinates and the edge weights will be integers;

I add two more decision variables: $O^X = \{{O^X}_{12}, {O^X}_{13}, \dots, {O^X}_{21}, {O^X}_{23}, {O^X}_{|V|(|V|-1)}\} $ and  $O^Y = \{{O^Y}_{12}, {O^Y}_{13}, \dots, {O^Y}_{21}, {O^Y}_{23}, {O^Y}_{|V|(|V|-1)}\}$ where ${O^X}_{ij}$ is the offset of the $x$ coordinate of a node $j$ with respect to node $i$. The same goes with $y$ coordinates as well.

For instance, if $x_i = 3$, $y_i = 4$, ${O^X}_{ij} = 2$, ${O^Y}_{ij}j = -1$ then $x_j = 5$ and $y_j = 3$.

As for the constraints, I have written:

\begin{matrix}
\forall \{i,j\} \in E;\\
x_j = x_i + {O^X}_{ij}\\
y_j = y_i + {O^Y}_{ij}\\
|{O^X}_{ij}| + |{O^Y}_{ij}| = w_{ij}
\end{matrix}

My logic behind that approach is as follows:

Since all the coordinates are integers, we are able to assume that we place the graph on a grid.
If the Euclidean distance between $i$ and $j$ is $2$, and $i$ is on $(x,y)$ point, then $j$ should be on one of the following:

\begin{matrix}
(x-2,&y+0)\\
(x-1,&y-1)\\
(x-1,&y+1)\\
(x+0,&y-2)\\
(x+0,&y+2)\\
(x+1,&y-1)\\
(x+1,&y+1)\\
(x+2,&y+0)
\end{matrix}

Of course, this is just an approximation to the actual solution.

However, the tool I work with (IBM ILOG CPLEX) does not give a solution.

I think I am mistaken somewhere.

**Note:** The above model (entitled as "I came up with something" is **not** what I am trying to achieve.
However, I could not find a better way to impose convex constraints.


texts:
I am a student and I was reading Numerical Analysis by Burden. In one of the exercises, I have to calculate $e^{-5}$ in two ways.

The first is using the Taylor's series for $x=-5$, $( e^{-5} = 1 - 5/1! + 5^2/2!-...)$ and second way is calculating $e^5$ and then $e^{-5}=1/e^5$,  again using Taylor's series but this time for $x=5$. In his solution, he says second way gives better results because we avoid subtraction. I think that it has to do with the floating point system but I am not very sure so I thought someone could further explain it to me. (Sorry if I have made any mistakes. English is not my native language)


texts: What language does this deterministic finite automaton accept?

texts: Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If anyone has any idea what language this automaton accepts it would really put my mind at ease.


texts: Differences and relations between high-performance/throughput computing and parallel computing?

texts:
I wonder if high-performance computing and parallel computing always mean the same?
If not,

what are the differences and relations between  them?
what are some examples of high-performance computing that are not parallel computing?
what are some examples of parallel computing that are not high-performance computing?

Are high-throughput computing and high-performance computing the same concept?


texts:
I'm studying for my theory of computation exam and came accross the following question:

Construct an appropriate Turing machine for the following language and prove or disprove it's semi-decidability:

$A := \{w \in \{0, 1\}^*\  |\  \exists x \in \{0, 1\}^* .f_w(x) = |x| \}$

The way I interpret this is that $A$ consists of all TM encodings $w$ which describe a TM $M'$ that for at least one input $x\in\{0, 1\}^*$ outputs the length of $x$. So now I try to come up with a TM $M$ for $A$, this TM should simulate TM encodings $w\in\{0, 1\}^*$ and check whether the TM $M'$ it simulates computes $f(x) = |x|$ for at least one $x$. In order to do this, $M$ would have to try computing all possible inputs for $M'$ and check if $f(x) = |x|$ is true for at least one input, if such an input $x$ exists than $M$ will terminate and accept the encoding of $M'$ which is $w$. If such an input $x$ doesn't exist then $M$ will keep simulating $M'$ forever and therefore won't halt. Hence I conclude that $A$ is semi decidable since it halts if a solution exists and otherwise doesn't.

Does this make any sense?

Also, since I need to prove/disprove $A$'s semi-decidability, I conclude that $A$ is not decidable (Rice's theorem), is that correct?


texts: Reference Request: Distributed Systems Systems

texts: I recently finished Operating System Concepts. As a follow-up for self-teaching, I am looking for a book on distributed systems (not theory). I've found Tanenbaum's text but it has rather poor reviews. I'm hoping for something with a similar flavor to Concepts: focusing on the general principals and concepts for building systems, without getting too technical.


texts: Is the isometric path cover problem NP-complete?

texts: Isometric path (like geodesic) is yet another name for shortest path. An isometric path cover is a set $S$ of isometric paths such that every vertex $v ∈ V$ belongs to at least one isometric path of $S$. The isometric path cover problem is to find a minimum cardinality isometric path cover of $G$. Is the isometric path cover problem  NP-complete for general graphs?


texts: NFA designing for strings starting with $01$

texts:
The question was asked

Construct an NFA with set of all strings that start with $10$.

The solution provided to me is

But my question is what if the automaton receives an input $0$ at the starting? Also there is no option for $q_1$ to transit after receiving $1$. So I think the solution should be

Please correct me if I am wrong.


texts: Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma

texts:
Question:

L is a language defined as $\ L = \{1^l | l\in primes\}$  (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory of closure or the pumping lemma to prove this.

My try:

So far I have tried to take a word $\ w  | w=1^p$ ($\ p$ being the pumping value), but in this case I don't know how to prove that every decomposition of the form  $\ w=xy^i z$ is invalid. When  $\ |y|=p$ (and therefore  $\ x=z= \epsilon $) the lemma is clearly untrue, because when  $\ i = 2$,  $\ |w'| = 2p$ which is not prime. But in the case that  $\ y<p$, and  $\ x \neq \epsilon$ and/or  $\ z \neq \epsilon$, I don't see a way to prove that  $\ w' = x y² z$ is not prime.


texts: Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves

texts:
This is the problem statement I came across today.

Given a binary tree, find the lowest common ancestor of all deepest leaves.

I came up with a correct algorithm, but I would like to confirm the running time of this approach.

The algorithm is as follows:

Traverse the tree and find the deepest level of the tree, dmax.
Traverse the tree and find all leaves at depth dmax.
Given that LCA(A,B,C) = LCA(LCA(A,B),C), traverse all nodes found at step 2 and calculate LCA.

The subroutine for LCA(A,B) is simple. Starting at A, go all the way up to the root and store each visited node in a hashset. Then, starting at B, go up until you find a node which is contained in the hashset.

I know the first two steps of the algorithm are both O(n), where n corresponds to the number of nodes in the tree. However, I am uncertain about the last step.

LCA(A,B) subroutine has a linear complexity. But how many nodes, in the worst scenario, can be found at step 2?.

Intuitively, I would argue that it has to be far less than n nodes.


texts: Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?

texts: How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?


texts: Convert the Finite Automata (FSA) into its equivalent regular expression, using stepwise minimization

texts: I was doing an assignment of Theory of automata but while doing this question I am stuck there is no such state that can be eliminated even from transition table. I am very confused and stuck please help me out


texts: Karp hardness of searching for a matching cut

texts:
Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split

Maximum Matching Cut problem
Input: An undirected graph $G(V, E)$ and an integer $k$
Output: YES if there exists $M \subseteq E$ such that $M$ is a matching of size $k$ (i.e. $k$ edges) and also a cut, NO otherwise

What is the complexity of this problem? (Turing completeness was established, what can we tell about its Karp hardness?)

An edge cut is a subset of $E$ the removal of which would increase the number of connected component of $G$, and for each edge in the set, its two endpoints are in (two) different components.


texts: What is so special about a majority and why is it the key for Paxos to work? (Paxos made simple)

texts:
Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was wondering, what is so special about a majority of nodes having a value? Why is that the key fact for consensus to work on Paxos?

It says on the paper that "any two majorities have at least one acceptor in common, this works if an acceptor can accept at most one value" (page 2). Its true that if we have two majorities then at least one node between the two must be the same one, but I was not entirely sure if I fully appreciated why that was special for consensus. How does this guarantee that a single value gets accepted? Or how does it aid in that goal?

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research


texts:
Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the availability of a polynomial algorithm for each NP problem indirectly?

edit:
I know that when NP-complete problems have polynomial algorithms, all NP problems must have polynomial algorithms. The question I am asking is that whether we can use the discovered algorithm for NP-complete to all NP problems just by modifying the algorithm. Or would we just know that NP problems must have a polynomial algorithm indirectly?


texts: Do height-balanced binary trees have logarithmic depth?

texts:
A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.


texts: How does cache partitioning prevent covert/side-channel attacks?

texts:
In a report on an open-source separation kernel (Muen kernel) I was reading,
in the future work section, it says that cache coloring can be implemented to prevent covert/side-channel attacks.

It is mentioned that

  In a second step each subject is associated with a color. All subjects of a given color share the same cache partition. In turn subjects of differing color have no access to identical cache locations, which means the cache cannot be used as a side-channel.

I understand what page coloring/cache partitioning is, but I do not understand how having different subjects use different cache partitions can solve side-channel attacks. Can anyone enlighten me on this?


texts: How is amorphous computing different from spatial computing?

texts: Surely spatial computing and amorphous computing share similarities and overlap. Is spatial computing a subset of amorphous computing? How are the two different?


texts: Minimal set of subintervals that 'covers' any subinterval in K subintervals

texts:
I have a big interval $I = [a, b]$ of size n.

I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most $K$  subintervals - specifficaly I'm interested in $K = 3, K=5$ only, but general solution would be interesting too.

In other words, for any subinterval $i$ of $I$ I want to take at most $K$ (3, 5) elements of $S$ to get $i$. So if $i = [2, 28]$, one can take for example $[2, 10], [10, 20], [20, 28]$, if such subintervals exists in $S$ and $K=3$.

I've come up with solutions that are in $O(n^2)$ where $n = |I|$, but that is the same as naive approach of taking all the subintervals. I can get to about $1/K$ of that by having intervals of size $m$ to generate also the $K$ bigger intervals, but it seems it is in the spirit of the puzzle to have asymptotically better solution than $O(n^2)$, at least for $K=5$.


texts:
For the following question:

If B is an element of PSPACE and A is an element of PSPACE-Complete, and A polynomial reduces to B, then B is an element of PSPACE-Complete.

I am trying to prove this, but I don't understand how to get started. Can anyone help please?


texts: Are problems that are fractions of constraints of NP-complete problems also NP-complete?

texts:
We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes,

is there a Hamiltonian path of size $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?
is there an independent set of size $b$ in  $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?
is there a clique of size $k$ in $\frac{n}{2}$ or of $\sqrt{n}$ or any number of nodes less than $n$?


texts: How are partial measurements performed on a N qubit quantum circuit?

texts:
I am trying to understand quantum computing concepts and have gone through alot of websites and books such as: Quantum Computing by Mikio and https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lecture1.pdf
So I do understand conceptually how to make measurements but I have enclosed images of a circuit i devised for an example and I am not able to attain the result of stage 5 (which is the output of the 1st two qubits only) when represented as matrices?. No paper/text explains this concept with proper examples. Any help is deeply appreciated. I have posted a similar question on the physics forum but they denied to respond as they assumed it some homework problem and had other issues. I am stuck and unable to move forward from here. Also it is not an assignment or anything. Thank you for your help.


texts:
What is the time complexity Big-O of this algorithm?

, The first assumption it's O(N * lg N) but it is not correct, why?

        count = 0
        for i = N : 1 {
            for j = 0 : i {
                count = count + 1
                j =  j + 1
            }
            i = i/2
        }
        print(count)


texts: Push down automata for $\{a^n b^n c^n | n \ge 0\}$

texts:
I am learning about context free languages.

I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's.

Intuitively however it seems that a pushdown automata to recognize $\{a^n b^n c^n | n \ge 0\}$ can be constructed. This PDA would initially push two $a$'s into its stack whenever it sees an $a$ in the input. It would change state when it first encounters a $b$ and pop a single $a$. It would continue to pop $a$'s for every b in the input until it encounters a $c$. It would again change state and pop single $a$'s for every c encountered. If the stack is empty at the end of the input the language is recognized as $\{a^n b^n c^n | n \ge 0\}$.

There must be something I am overlooking whilst constructing the PDA as a language is context free if its has a PDA recognizing it. Please point out my mistake.


texts:
Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where $n$ is fixed and known for given $f$. To query $f$, an element $x$ (the guess) from $$\{0, 1, ..., n - 1\}$$ is provided, and the value returned is $(f_S - x) \mod n$. Additionally, the state $f_S$ of$f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

By making uniformly random guesses with each query, one would expect to have to make $n$ guesses before getting $f_S = x$, with variance $n^2 - n$ (stated without proof).

Can an algorithm be designed to do better (i.e., make fewer guesses, possibly with less variance in the number of guesses)? How much better could it do (i.e., what's an optimal algorithm, and what is its performance)?

An efficient solution to this problem could have important cost-saving implications for shooting at a rabbit (confined to hopping on a circular track) in a dark room.


texts:
Consider the following expression :-
$$h(h^{−1}(L))$$

I need an example where this expression can be superset of subset of L,but i am not able to get one.I am getting this equal to L always.How can i approach this?


texts: Program to check whether a string is accepted by an unrestricted grammar

texts: How can I write a program to find out whether a given string is generated using a type 0 grammar (unrestricted grammar)?


texts:
Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value.

We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v).

For example, the cumulative sum of d in the following DAG is 7:

      a (2)
     / \
    v   v
(1) b   c (3)
     \ /
      v
      d (1)

Is it posible to compute the cumulative sum for a set of M nodes in G, in less than O(M*(N + E))?

Clarification: computing the cumulative sum for a set of nodes refers to computing the cumulative sum for each node of the set.

Further clarification: for a given cumulative sum, each ancestor is counted only once (notice that the ancestors of $u$ include $u$):

$cumsum(v) = \sum_{u \in \text{ancestors of } v} \text{value of } u$

Which does not imply:

$cumsum(v) = \text{value of } v + \sum_{u \in \text{direct ancestors of } v} cumsum(u)$

because this last formula may count ancestors multiple times. For example, in the diamond example we have:

$cumsum(d) = 7$
$cumsum(b) = 3$
$cumsum(c) = 5$
so $cumsum(d) \neq 1 + cumsum(b) + cumsum(c)$

Solution in O(M*(N + E)):

  To compute the cumulative sum of a single node v in O(N + E), sort the
  DAG topologically and traverse the sorted list of vertices backwards,
  tainting all ancestors of v with the back edges, and adding the values
  of all the ancestors. (You could also just do a DFS for the same
  price).

  Doing this for each node in the given set of M nodes gives a running
  time of O(M*(N + E)).

  Although it doesn't affect the final running time, the topological
  sort could be done only once before looping through each cumulative
  sum calculation.


texts: For proving that L is in NPC, why do we reduce a known L' into L and not the other way around?

texts: For proving that $L$ is in NPC, why do we reduce a known $L'$ into $L$ and not the other way around i.e. reducing $L$ into $L'$.


texts:
Is $NC_1$ vs PP still an open problem?
I done a few searched but I can't find an answer.


texts: How to rank these functions in increasing order of complexity [Algorithms]?

texts:
I have the following functions:

What is the correct order of these functions in increasing complexity?
I could always start entering values in these functions and check the corresponding output to notice the rate of increase. But is there a better, faster way of ranking these functions in order of increasing complexity? For example are there rules of thumb I could use to quickly sort these in order of increasing complexity? (Like I know generally exponential functions are more complex than log functions)


texts:
Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$.

I just wanted to check if my grammar is correct or not.

$$A \rightarrow 1B1$$
$$B \rightarrow 0B0\;|\;1B\;|\;0B\;|\;A\;|\;\epsilon$$


texts: Application Ambiguity in Untyped Lambda Calculus

texts:
So, untyped lambda calculus has the following formal grammar for its terms:

$$e::= x \mid \lambda x . e \mid e_1 e_2$$

Usually this is presented in some ML-esque language as (using de Bruijn indices)

data term = variable Nat | lambda term | apply term term

My question is: apply (variable Nat) term is syntactically valid, but the rator is just a free variable, isn't this an invalid expression? If not, what does it evaluate to?


texts: Can a regular language enforce a length limit AND disallow consecutive characters?

texts:
I was reading the venerable "How to Find or Validate an Email Address [using Regex]", and I came across the following statement at the bottom of the page:

  [A] true regular language cannot enforce a length limit and disallow
  consecutive hyphens at the same time.

This seems wrong to me.

I feel like if the length of a string is bounded ahead of time, you should be able to write a DFA which processes pretty much any rule on the input string, as you can just create $n$ states from the most recent states, where $n$ is the number of letters in the alphabet, repeating for the maximal length of the input string?

If this reasoning is wrong, can someone point me in the right direction?


texts: Show that the following language is undecidable

texts:
$\{ M \mid M
\text{ is a machine that runs in }100n^3 + 300\text{ time }\}$

I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first is undecidable then building an instance of the first problem starting from the second, ie asking if a machine M that executes an input n stops after a time $f$$(n)$ is like asking if it stops at all and then M ⊆ HALT. However there is something that does not convince me in this demonstration because it seems quite naive and I don't think that this is enough to prove that this language is undecidable. In addition the exercise it is taken from a chapter of a text in which the oracles are introduced, is it possible to prove this language undecidable by means of oracles? I would appreciate your help, thanks.


texts: Composition on functions computable in logspace requires always inner recomputation?

texts:
We have a composition logspace computable functions where the outer machine is one-way and the inner is a logspace verifier with a read at once certificate tape and output string (instead of "yes" or "no" answers). One of my colleague told me it is obligated to recompute the certificate tape since for this composition, you need to read the certificate many times, and thus does not work, since it is on a oneway tape and I am saying that it is not necessary and this actually never happens because the outer machine is one-way.
I want to know if my explanation is (almost) correct or I am (partially) wrong and maybe some pieces of advice or verifiable facts to deal with that person which I'm trying to convince him (Thanks in advance), please.


texts: How to choose symbols to replace for this left-most derivation?

texts:
I have a context free grammar such as the following:

$E→E+T | T$
$T→T×F | F$
$F→(E) | a$

Using the left-most derivation, the following can be derived:

$E⇒E+T⇒T+T⇒F+T⇒a+T$
   $⇒a+F⇒a+(E)⇒a+(T)$
   $⇒a+(T×F)⇒a+(F×F)$
   $⇒a+(a×F)=a+(a×a)$

I know what the left most derivation is and I know what the grammar notation means but what I am trying to understand is how should I substitute the symbols in correct order? For example:

I start with:

$E⇒E+T$

I substitute 'E' first on the left and it becomes:

$⇒T+T$

Then I need to substitute $T$ on the left and it becomes:

$⇒F+T$

Why $T×F$ wasn't chosen to replace $T$ and why $F$ in this case?

Also, in the very next step $F$ was replaced by $a$ and why it wasn't replaced by $(E)$?


texts: Advantages of Lambda calculus over Turing machine and vice versa

texts: What kind of advantages does Lambda calculus have over Turing machine, and vice versa?


texts: Removing recursion from a function with multiple params

texts:
I am given the following function as a brain teaser:

def t(x, y, z):
    if x <= z:
        return y
    else:
        return t(t(x  - 1 , y  , z ) , t(y  - 1 , z  , x ) , t (z  - 1 , x  , y ))

the task is to remove the recursion in the else-branch. the only allowed expressions are of type arithmetic (+,-,*,/,%), logical (&&,||,!),
relational (<,<=,==,>=,>,!=) and if-else.

My first approach was to order the input in lexicographical order and trying to deduce a relationship which seemed to look like like this initially:

else:
    if y > x
        return x
    else:
        return z

but that does not work, a counterexample is t(20, 7, 18)=8. So the underlying relationship seems to be a bit more complex. I have also tried to formally infer the solution by differentiating the cases for the '>'-relation between the variables but I did not get far with that either.


texts: What is meant by the statement "Data is inactive but information is active"?

texts: I came across the statement "data is inactive but information is active" while reading differences between data and information. What is meant by this statement?


texts: What does it mean if a generic structure is type-erased?

texts: This documentation states that the generic structure AnyIterator is a type-erased iterator of Element.


texts: how to prove that every finite language is context-free?

texts: I am trying to prove that every finite language is context-free, is there any type of way that I could do it effectively?


texts: Prove by induction that the running time of recursive Fibonacci is exponential

texts:
This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! But I am finding it difficult to fully understand how to prove things involving lower and upper-bounds. After looking up many resources including some things from Stanford, this is what I have been able to come up with:

Let $T(n) =$ time for $fib1(n)$, where $T(n) = T(n-1) + T(n-2) + 3$

Claim: For $n \ge 6$, the running time of $fib1(n)$ is exponential, i.e $T(n) \ge (1.41)^n$

Base Case: $$T(6) = 8 \ge (1.41)^6 = 7.86$$
               $$T(7) = 13 \ge (1.41)^7 = 11.08$$

Inductive Hypothesis: Assume that for an arbitrary n, $T(n) \ge (1.41)^n$

Prove $T(n+1) \ge (1.41)^{n+1}$:
$$T(n+2) = T(n+1) + T(n) + 3$$
$$\ge 1.41^n + 1.41^{n+1} \text{  [By the I.H]}$$
$$ = (1.41^n)(1+ 1.41) > 1.41(1.41)^n$$

Thus, the running time of $fib1(n)$ is $\Omega{(1.41^n)}$

Edit:

I'm not entirely sure how correct this is, but I'm not as worried about that. My main concern is in the induction step, I feel like there is something I am missing conceptually. Specifically, how exactly can we be sure that $$T(n+2) = T(n+1) + T(n) + 3 \ge 1.41^n + 1.41^{n+1} $$ if we only know that $$T(n) \ge 1.41^n$$

I hope this clarifies my question. Thanks!


texts: Generalized operators for programming languages

texts:
After asking this question on stackoverflow, it has changed slightly.  Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that vector space?

I'm interested in the parallels between mathematical operators (like the Hamiltonian, ladder operators, momentum operators, etc) and programming languages.  The operators that I'm talking about can be thought of as transformation matrices that act on (potentially) infinite vectors.  It seems like a good place to start might be a tree algebra?

An alternative would be to force the program into some sort of allowed bitwise representation, and then perform transforms on it.  Is such a thing possible?


texts: Data structure used to implement recursion

texts:
Which data structure can be used to "eliminate" recursion from a recursive program? Array, stack, queue, or list? How is it used to that end?

When I eliminate recursion from the program computing factorial $n! = n(n-1)!$, I replace recursion with a loop. But I don't see how to do a similar transformation in general.


texts:
First off - I'm not a Computer Scientist, I'm a Software Developer - so when it comes to presenting an idea in a formal manner to a Computer Scientist, I have no idea how to do so. As such, I'm wondering if someone would be good enough to show me how to write the algorithm/idea I've outlined below in some form of formal alogrithmic notation, please?
Part One:
Say I have a list of 'words' made up from characters of the English alphabet. Essentially, I want to split this list of 'words' up into twenty-six sub-lists, where each sub-list is associated with one letter of the alphabet - a, b, c, etc. Each 'word' should be moved to the sub-list associated with the character that the 'word' begins with - so 'apple' would go in the 'a' sub-list, 'banana' would go in the 'b' sublist, etc. BUT, I only want to divide my original list up into sub-lists provided that there are at least X 'words' in the list that begin with each letter of the alphabet (so if X was 2, there would need to be at least two words beginning with 'a', at least two words beginning with 'b', ..., at least two words beginning with 'z', etc.). In essence, it's either one list with all 'words' in it or 26 sub-lists with at least X 'words' in it.
Part Two:
Assuming I was able to split the list of 'words' up into sub-lists as described in Step One, I then want to further divide each sub-list based on the value of the second character in each 'word'. So there would be an 'aa' sublist, an 'ab' sublist, ..., a 'zz' sublist, etc. Again, I only want to do any further division of the sub-lists provided there are at least X 'words' that begin with every possible two-character combination of English alphabet letters - so at least two 'words' beginning with 'aa', two 'words' beginning with 'ab', ..., two words beginning with 'zz', etc. In essence, it's either 26 sub-lists or 676 sub-lists.
Part Three:
I want this dividing process to continue (character three, character four, etc.) until it is no longer possible to satisfy the criteria that there are at least X 'words' in each sub-list that 'begin' with every possible combination of the number of characters that are currently under consideration.
For argument's sake at this point, it can be assumed that all 'words' are the same length.
Any help is very much appreciated.


texts:
Consider the example of solving for $x$ where $Ax=b$.  This is not in general function, there can be more than one solution.  So if you make such a solver in a functional style...does this count as a side effect?

def solve(A:Matrix[Float],b:Matrix[Float]):Matrix[Float] = ...

Obviously the solution will be dependent on several internal factors such as the method to solve, e.g. the type of echolonization, or perhaps it uses randomization (Krylov methods for example).  And that appears to be all you could expect because solving is not a function.  Still, it is evident that the return is a representative of an equivalence class, and so subject to the interpretation that the outputs are representative of an equivalence class then this would be a function -- just we don't want to implement it as some coset of a subspace as that might be slower or impossible.

In purely functional programming is there a loop-hole of sorts for implementing relations -- which interpretted under an equivalence relation, become fucntions, even if we don't explicitly wrap it up that way?

E.g. could I implement a version of the signature above for solve in Haskell without a monad?


texts: Suppose I have two union-find trees with roots $x$ and $y$ respectively. I want to join them in constant time (this is normally possible since I already "hold" the roots) but I need $x$ to be the root of the merged tree. I don't know what rank $x$ or $y$ have (or more precisely formulated I need this to work always - for any $x$ and $y$ I want the final tree to have $x$ as its root). Is that possible? I couldn't find a solution to this, but it's really not my day today :)


texts: How to minimize the number of gates of an arithmetic circuit?

texts:
A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices.
Consider an arithmetic circuit where the only operations are addition ($+$) and multiplication ($\times$) over some ring, say, the integers modulo $N$.

Now, if I understand correctly, any circuit can be thought of as a multivariate polynomial. For instance this circuit:

x    2    y
\    /\   /
 \  /  \ /
  *     *
   \   /
    \ /
     +
     |
     z

can be expressed by the polynomial $z = f(x,y) = 2x + 2y$. Another way of representing this polynomial is as $z = f(x,y) = 2(x+y)$, which as a circuit has less gates since it only has one addition and one multiplication.

As we saw above, by exploiting some algebraic relations like factoring the number of gates can be reduced, however, in general multivariate polynomials cannot be factored, so seeking for a factorization is not a general way of minimizing the number of operations.
Also, factoring is not always the solution. For instance, consider the polynomial $f(x,y) = (2*x + y)*(2*x-y)$, which has $5$ operations. If we expand it we get $4*x*x - y*y$, which has 4, so in this case factoring does not help.

There are some other optimizations like noticing that $\underbrace{x+x+\cdots +x}_{n\text{ times}} = n\cdot x$, or $a+(b+x) = (a+b)+x$, where $a,b$ are constants (so $a+b$ does not count as an operation).

Applying all these optimizations (and many more!) to a complete circuit with many variables seem very tricky.
I'm sure this is a well studied problem in computer science. My question is

  Given a circuit, how do we minimize the number of gates? Are there algorithms/tools for this purpose, or is it proven to be a hard problem?


texts: I am newby at Prophet model. I was wondering Prophet uses stochastic or batch approach while in training. If it uses stochastic that means there is nothing to do convert and compute mini batch gradient descent. I would like to implement mini batch gradient descent to compute cost every iteration and update model parameter in order to incerease accuracy and minimize the computation cost.


texts:
I think I have a passable understanding of what Big-O and little-o mean. I'm just wondering whether it makes sense notation-wise to state something like the following:

$$O(n^c) = o(n^k) \text{ for } k > c$$

For example, $O(n^2) = o(n^3)$ since $3 > 2$. Basically, any constant times $n^2$ will still grow more slowly than any constant times $n^3$ for large enough $n$.

Does it make sense to have both sides of an equation consist of big-O and/or little-o notations like this, or does one side of the equation have to consist of a bare function only? Thanks.


texts: Why decision tree method for lower bound on finding a minimum doesn't work

texts:
(Motivated by this question. Also I suspect that my question is a bit too broad)
We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison and each leaf is a permutation. Since there are $n!$ leaves, the minimum tree height is $\Omega(\log (n!)) = \Omega (n \log n)$.
However, it doesn't work for the following problem: find a minimum in the array. For this problem, the results (the leaves) are just indices of the minimum element. There are $n$ of them, and therefore the reasoning above gives $\Omega(\log n)$ lower bound, which is obviously an understatement.
My question: why does this method works for sorting and doesn't work for minimum? Is there some greater intuition or simply "it just happens" and we were "lucky" that sorting has so many possible answers?
I guess the lower bound from decision tree makes perfect sense: we do can ask yes/no questions so that we need $O(\log n)$ answers: namely, we can use binary search for the desired index. My question still remains.


texts: Finding an instance of an n-element set cover

texts:
Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter line 3 so that it would run until the size of C was equal to n, and change the logic in line 4 so that it would pick and remove vertices until the size of n. A vertex would be removed when the size of C doesn't equal to n but the cover is complete. I can't really think of any other way to do it. The real problem is that I'm not entirely sure how to make the algorithm run in exponential time like they are asking.

  GREEDY-SET-COVER can return a number of different solutions, depending on
  how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE.n/
  that returns an n-element instance of the set-covering problem for which, depending
  on how we break ties in line 4, GREEDY-SET-COVER can return a number of
  different solutions that is exponential in n.

  $X$ — some finite set
  $F$ — a family of subsets of $X$
  $C$ — cover being constructed

  GREEDY-SET-COVER($n$)
  1    let $U = X$
  2    let $C = \varnothing$
  3    while $U \ne \varnothing$
  3a            select an $S \in F$ that maximizes $\left|S \cap U\right|$
  3b            set $U = U \setminus S$
  3c            set $C = C \cup \{S\}$
  4    return $C$

Could it be said that since the number of subsets a set has is $2^n$ and that in the worst case this algorithm will end up finding all of those subsets before settling on an n-instance set to return?


texts:
I'm trying to understand what a random binary tree is. According to Wikipedia:

  Two different distributions are commonly used: binary trees formed by
  inserting nodes one at a time according to a random permutation, and
  binary trees chosen from a uniform discrete distribution...

If I start with a root and then append nodes randomly with no consideration to depth. Would that be considered a random binary tree? Or am I missing something?