texts: Find all the special graphs which can reduced to the shortest paths graph

texts:
I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative cycle.

An execution of some algorithms will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. For instance, Floyd–Warshall algorithm is straightforward, and it works. Let us denote the result by $G' = (V, E, W')$.

In $G'$, it is possible that for an edge from $i$ to $j$, $w'(i,j) = w'(i, k_0) + w'(k_0, k_1) + \dots + w'(k_n, j)$. Let us make from $G'$ another graph $G''$ whose any element is same as $G'$ except $w''(i,j) = \infty \neq w'(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G'$.

So given a $G'$, I would like to find all the graphs like $G''$, such that for all $i$ and $j$, $w''(i,j) \in \{ w'(i,j), \infty\}$, and $G''$ can be reduced to $G'$ via a shortest paths algorithm.

Hope my question is clear... I do not know if an algorithm for this exists already, does anyone have any idea?


texts:
My professor gave an example of Huffman tree.

Given inputs

a 80
b 10
c 20
d 50
e 100
f 35
g 60

… then the tree will be:

But when i tried to solve it at home, I get this answer:

Which is correct, and why?


texts:
For any language $L \subset \Sigma^*$, define $S(L)$ to be $$\{x\in L \mid \neg \exists y \in L: \exists z \in \Sigma^*: (z \ne \epsilon) \land (x=yz)  \}$$

Show that $S(L) = S(S(L))$

I'm confused about the question here. The way we define $S(L)$ takes elements from $L$ $(x \mid x \in L)$, but $x=yz$ and $y \notin L$. How is it possible for x to concatenate an element from $\bar{L}$ (complement of $L$ since $y \notin L$) and still be an element of $L$?


texts:
I've read that "Every problem in NP can be reduced to every NP-complete problem".

My question is on the choice of the word "reduce". If I were to "reduce" a polynomial problem in NP to an exponential problem in NP, I just plain feel weird about using the word "reduce" because I feel like I've increased the problem, not reduced it. So, why do we use the word reduce?

Also, why do we write "reduce A to B" as $A\le_{p} B$. It seems backwards.


texts: Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?

texts:
Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and language accepted by the PDA is union of these two?

For example, Consider the PDA shown below:-

I was trying to figure out the language accepted by this PDA and I got confused on the point that a string w=b is given as input, that will be popped out and the stack will be empty so would b be an element of language accepted by PDA or if we consider it only as acceptance by final state (considering that acceptance by final stack requires the bottom of stack symbol to be left in the stack ) the language accepted by this PDA will be :

{w| any prefix of w has number of a's more than number of b's}

However a string like "ab" can also be accepted if we allow both acceptance by empty stack and final state (The confusion here is strictly more a's or it can be equal too).


texts: Understanding time complexity of a while loop that will look over all vertices and edges

texts: I need a little clarification on differing time complexities. My analysis for the below algorithm was $O(n +nm)$, but the correct analysis would be $O(n+m)$. I know that Color takes $O(n)$ time to initialize and the inner for loop takes $\mathrm{deg}(v)$ time, which by the handshaking lemma, wouldn't the inner for loop then be $O(m)$ and since the outside while loop iterates over all vertices in worse case so shouldn't that be $O(n)$, Giving $O(n) + O(nm)$?


texts:
The recurrence equations solved by the Master Theorem are in the following format :

$ T(n) = a T(\frac{n}{b}) + f(n)  $

but is it possible to use it on :

$ T(n) = a T(\frac{n}{b}) + c  $

?


texts: Controlling overflow and loss of precision during floating point multiplication

texts:
I have a large number of floating point numbers (~10,000 numbers) , each having 6 digits after decimal. Now, the multiplication of all these numbers would yield about 60,000 digits. But the double range is for 15 digits only. How can I get my product with minimum loss in precision?

I thought of storing the numbers as 6 digit long long integers and storing their exponents elsewhere. But this appears cumbersome and may not yield correct result. Is there an alternate easier way to do this?


texts:
Say you have 3 objects, a global MemoryStore, which has an array of MemorySlabCache objects, and each MemorySlabCache has an array of MemorySlab objects. Sort of like this:
class MemoryStore {
  caches: Array<MemorySlabCache> = []
}

class MemorySlabCache {
  size: Integer
  slabs: Array<MemorySlab> = []
}

class MemorySlab {

}

But the thing is, this doesn't capture everything. It also needs to capture the fact that each MemorySlabCache has a size, which is used to tell what size the MemorySlab objects are it contains. So it's more like this:
class MemoryStore {
  caches: Array<MemorySlabCache> = []
}

class MemorySlabCache {
  size: Integer
  slabs: Array<MemorySlab<size>> = []
}

class MemorySlab<size: Integer> {

}

Then we create our caches:
let 4bytes = new MemorySlabCache(size: 4)
let 8bytes = new MemorySlabCache(size: 8)
...
let 32bytes = new MemorySlabCache(size: 32)
...
store.caches.push(4bytes, 8bytes, ..., 32bytes, ...)

Does this count as a "dependent type", "a type whose definition depends on a value"? Since the type of the Array<MemorySlab<size>> is dependent on the value assigned to the size field on MemorySlabCache. If not, what is this? What would make it into an example of dependent types?


texts:
Is the language $A$ decidable ?  Please help me get the proof right !!

$A = \{ \langle  M \rangle | M \text{ is } TM \text{ such that } L(M) \neq \Sigma^*  \}$

My proof is by contradiction. Assume $A$ is decidable and let $R$ be decider for it. I will construct decider $S$ for $A_{tm}$, using $R$ as a subroutine.

S = on input <M,w>
constructs M_w = on input x
 if x!=w accept
 else run M on w
  if M accepts => accept
  else => reject
run R on M_w
 if R accepts => reject
 if R rejects => accept

Note : If $M$ accepts $w$ then $L(M_w) = \Sigma^*$ , then $R$ ran on $M_w$ will reject it, and $S$ will accept.
If $M$ rejects or loops on $w$, $L(M_w) \neq \Sigma^*$, then $R$ ran on $M_w$ will accept, and $S$ will reject.
Therefore, we created a decider for $A_{tm}$, but we know that $A_{tm}$ is undecidable, our assumption was wrong => $A$ is undecidable .


texts: How to judge the searching precision of Particle Swarm Optimization?

texts:
As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, the precision of grid ergodic searching is the searching step. But what the precision should be using PSO searching. From the position update formula of PSO:

$x_i \leftarrow x_i+v_i$

So, we can assume the precision of PSO searching is the maximum of velocity of particles? Is this right?
Generally, we set the maximum of particle velocity is about 10% to 20% of the position scale. But with this setting, we can still obtain a good precision with PSO, which contradicts previous assumption. So the searching precision of PSO is? Or it can be expressed as a function of maximum velocity and other parameters?

It seems that PSO can realize arbitrary precision... Because if there are sufficient particle numbers and iteration times, the PSO can approach to the actual solution.


texts: Evolving artificial neural networks for solving NP problems

texts:
I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. They use genetic algorithms to "evolve" the weights of the axons.

So basically my idea is the following. If I was supposed to write a program that recognizes numbers I would not know how to start (I could have some vague idea but my point is: It is not trivial, nor easy.) but by using neural network I do not have to. By creating the right context in order for the neural network to evolve, my neural network will "find the correct algorithm". Down below I quoted a really interesting part of the article where they explain how each layer have different role in the process of image recognition.

  One of the challenges of neural networks is understanding what exactly goes on at each layer. We know that after training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. For example, the first layer maybe looks for edges or corners. Intermediate layers interpret the basic features to look for overall shapes or components, like a door or a leaf. The final few layers assemble those into complete interpretations—these neurons activate in response to very complex things such as entire buildings or trees.

So basically my question is the following: Couldn't we use genetic algorithms + neural networks in order to solve every NP problem? We just create the right evolutionary context and leave "nature" find a solution.

Inceptionism: Going Deeper into Neural Networks

EDIT: I know we can use Brute-Force or find a not-efficient solution in many cases. That is why I try to highlight Evolving artificial neural networks. As I said in a comment: Given sufficient time and an appropriate mutation rate we could find the optimal solution (Or at least that is what I think).


texts: How do I compute the huge numbers which occur in el gamal decryption?

texts:
I'm trying to do decryption using el gamal. The formula to get the message M is
$$ M=\frac{b}{a^x} mod \:P $$ In one case, we may have $$ M=\frac{18}{62^{62}} mod \: 71 $$ This value cannot be computed on a calculator as $62^{62}$ gives an infinite value. How do we get the value of M?


texts: How does the 3-opt algorithm for TSP work?

texts:
I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers that mention that when three edges are removed, there remain only 2 possible ways to recombine the tour - this doesn't make sense to me.

For example, I found a paper [1] that says:

  The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1 (ﬁgure 2 and ﬁgure 3). A 3-opt move can actually be seen as two or three 2-opt moves.

However, I count 3 different ways to reconnect the tour. What am I missing here?

Also, can someone link me to an algorithm for 3-opt if possible? I'm just trying to understand it, but I haven't come across any clear algorithms yet: all resources I find simply say "remove three edges, reconnect them". That's it, which is sort of vague.

Here are the 3 tours that seem to me to be 3-opt moves after removing three edges.

Heuristics for the Traveling Salesman Problem by C. Nilsson


texts: Given a Noisy Curve, Write a Function to Output Likely Slopes

texts:
I am training a Variational Autoencoder (type of convolutional neural network), and have been plotting cost over time. The result is a noisy curve, shown here:

I would like to write a function that gives the probability that the cost function has bottomed out, i.e. that its slope going into the future is zero. Due to the noise, I can't just take the derivative of the cost function, as it oscillates stochastically. I could take the derivative of the moving average of the cost function, but it would be unclear what window size to use, and regardless a single window size would be useful for only part of the line (the noise tends to increase over time).

Is there some mathematical function/theorem I can use to take the local noise of the curve into account, and output a range/distribution of probable slopes? I would imagine the output being something like a histogram with the most likely slope at the middle and increasingly less-likely slopes off on the sides.


texts: Any book for learning to correctly find out complexity of one's algorithm?

texts: Suppose we have designed an Algorithm and we want to find out its complexity. I am looking for a book which mainly focuses on finding out complexity of algorithms rather than introducing me to different search, sort, and ... algorithms.


texts: Using the pumping lemma for a specific language

texts:
Please help me with the following question:

Define the language LONGERB to be the set of strings over $\{a,b\}$ where the longest substring containing only $b$’s is strictly longer than the longest substring containing only $a$’s (e.g. $aabaabaaabbbba$ is in LONGERB because the longest substring containing only $b$’s has length 4 while the longest substring containing only $a$’s has length 3, while $ab$ is not in LONGERB). Let $n$ be the integer from the pumping lemma. How many of the following strings can be used in a pumping lemma proof that LONGERB is not regular?
(i) $abab^{n+1}$ (ii) $a^nb^{2n}$ (iii) $a^{10}b^{10}$ (iv) $a^nb^n$

The answer that has been given in the book is 3 (Options 1,2, and 4). But my doubt is, that the 4th option doesn't belong to the given language as there is an equal number of $a$'s and $b$'s in this option. So, according to me the correct answer should be 2 (Options 1 and 2 only).
Please give a proper reason for each of the four options, why it can or cannot be used to prove that the given language is not regular.


texts: Computing overlap of intervals in an integer programming framework

texts: Suppose I have 2 intervals C1 = [x1, x2] and C2 = [y1, y2], where x1,x2,y1,y2 are variables in an Integer program, I want to compute the overlap of C1 and C2. I am interested in a tight formulation for computing the overlap as an another variable with as few big M constraints as possible. Any references or formulations are deeply appreciated.


texts: Criteria based estimation of a task's due date

texts:
Basically we have a ticket system, each day we get multiple tickets with different categorization (Question,Change,Error) and importance (High,Mid,Low) for different customers (A,B,C). My job is to create some kind of a system determining the due date of these "tasks" based on

The state of the previous ones, completed or not.
The availability of the developers.
A criteria of the previously mentioned attributes (categorization,importance and customer
type).

knowing that each ticket has variable number of hours needed to finish it.

How can one achieve that?


texts:
Formally show that $0.1n + 10\sqrt{n}$ is not $O(\sqrt{n})$ using the definition of $O$ only.

I cannot find much on how to solve a problem like this, nor do i know how. Am I supposed to show some contradiction by trying to prove it is $O(\sqrt{n})$? Any help on how to answer this would be appreciated.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).


texts: how to maximise the no of edges selected in the graph in form of cycles of unbounded length?

texts:
Recently i started looking the perfect cycle cover algorithm related to kidney exchange problem where it is considered as NP-Complete for cycles restricted to a length>2. However if cycles are not restricted by removing the length constraint it is considered as solvable in polynomial time ,But if perfect cycle cover doesn't exist and just we need to maximise the no of edges selected in form of cycles(So as to maximise the no of kidney exchanges), also no restriction on cycle's length, then how do we do it?

I am thinking of finding all cycles in the graph and then one by one remove the cycle's edges from the graph and then find the cycles in the residual graph and so on till no more cycles exist and then sum up all the cycle's lengths continuing this for all cycles and find the solution with maximum edges selected. But since this is not a good solution i want to know how to solve this maximising problem


texts: Uniqueness of non-dominated two-dimensional points

texts:
This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions.

We say point $p_i=(x^i_1, x^i_2)$ dominates point $p_j=(x^j_1, x^j_2)$ if $x^i_1 \geq x^j_1$ and $x^i_2 \geq x^j_2$. Prove that if in a set of $n$ points there are no pairs such that one dominates the other, that the points can be ordered such that one dimension is strictly ascending and the second is strictly descending.


texts: In a lecture a professor mentioned that modern computers don't have as much computational power as a Turing machine because they don't have infinite memory, and since no computer can have infinite memory the Turing machine is therefore unattainable and simply represents the upper limit of computing. Is there a measure, or definition of what problems (or class of problems) lie beyond the reach of our computing power because of this?


texts: Perfect Matching in Bipartite Graph with mutually exclusive edges

texts:
Problem

I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.

Example

Left vertices: $a,b,c$

Right vertices: $x,y,z$

Edges: $(a,x),(a,y),(b,z),(c,y)$

Exlusive pairs: $(b,z)$ and $(c,y)$

Answer: no perfect matching

Question

Is the problem in P or NP?

Solution Attempts

I know that Perfect Matching in Bipartite Graph Problem is in P. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is NP, but without any luck.


texts: Is Dijkstras algorithm used in modern route-finding systems?

texts: Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?


texts:
I am learning about context free grammars and have been through few texts in a undetailed  manner  on these topic . I think I should know the exact , rigorous ,technical definition of what exactly a "grammar" means .

I could see that  ,in all of these lessons, a sequence of equations as follow :

 a = bc
 b = ed
 c = gh

I was tempted to conclude that "a grammar is a collection of symbols which are related by a set of equations which dictate rules for substitution of a symbol by a series of symbols "

Then I got to know that , not in all series of equations can we substitute one symbol by a series of another symbol .We can do it only in case of "context-free grammars " .
Then I went through one of the stackexchange post and through a brilliant answer got to know what context free exactly means .

So , I thought before I proceed ahead I better seek for the exact rigorous definition of a grammar .
What exactly is the mathematical/technical definition of a grammar ?


texts:
According to the Bell-Lapadula model, write access is only to Subject $S$ on object $O$ provided if:
$L(S) \leq L(O)$ where $L$ is the clearance level for $S$ and classification for $O$. This seams counter intuitive. Are there any attacks that this protects against and what other benefits are presented by it?


texts: What does "fast-forwarding" mean in the context of CPU simulation?

texts:
I'm using a simulator for my thesis and I've come across the term "Fast-forwarding" but I have found no definition anywhere in the documentation or online. From a pdf I've been reading about the simulator I am using (gem5), I've come across this section:

  The gem5 simulator supports four different CPU models: AtomicSimple,
  TimingSimple, InOrder, and O3. AtomicSimple and TimingSimple are
  non-pipelined CPU models that attempt to fetch, decode, execute and
  commit a single instruction on every cycle. The AtomicSimple CPU is a
  minimal, single IPC CPU which completes all memory accesses
  immediately. This low overhead makes AtomicSimple a good choice for
  simulation tasks such as fast-forwarding. Correspondingly, the
  TimingSimple CPU also only allows one outstanding memory request at a
  time, but the CPU does model the timing of memory accesses.

Does anyone know what this term actually means?


texts:
One time I saw a theorem that says something like any language can be partitioned into regular languages, but I can't remember exactly what the theorem is.
Could somebody tell me, is this true? What is this theorem?


texts: Reverse cartesian product matching all given rows

texts:
I´m looking for an efficient algorithm that will find reverse cartesian products.

Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \dots \times A_{i,n}$, for $i=1,2,\dots,k$; and I want to minimize the number $k$.  Is there an efficient algorithm to solve this problem?

This may be easier to explain by example.  Calculating the cartesian product (cross product) is trivial, e.g. {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5} results in:

    1 1 1
    1 1 2
    1 1 3
    .
    .
    .
    5 5 3
    5 5 4
    5 5 5

All 125 (5 x 5 x 5) rows are created.

Now let's say you remove some rows from this result, i.e. you are left with these 14 rows as a starting point:

    1 2 3
    1 2 4
    1 2 5
    5 2 3
    5 2 4
    2 2 5
    3 2 5
    1 3 3
    1 3 4
    1 3 5
    5 3 3
    5 3 4
    2 3 5
    3 3 5

Now, how do I find a cartesian product that if calculated can generate only those 14 rows back? (order of rows is irrelevant). It can no longer be represented by only one cartesian product {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5} since e.g. 5 5 5 is not in the list.

One way to now represent the rows as cartesian products is this answer:

    {1} x {2,3} x {3,4,5}
    union
    {5} x {2,3} x {3,4}
    union
    {2,3} x {2,3} x {5}

But the above merge of rows is not optimal although it is a valid solution, we can do better and write it in only two cartesian products:

    {1,5} x {2,3} x {3,4}
    union
    {1,2,3} x {2,3} x {5}

This result is better since 2 < 3 and I want to find the smallest possible number of cartesian products that still represents all the rows. There is no way to reduce (merge) this any further given the 14 rows so this is the best answer in this case.

Now if the starting point would have been all the 125 rows (as in example above) the optimal answer would have been one: {1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5}.

Some known facts about the input:

All rows are unique, no duplicates exists in the list.
Row are of same length, fixed with either 3,4,5,6,7,8 in length.
Numbers in a row range from 1 to 20
There could be millions of rows as a starting point but typically around 100k, hence speed is of importance rather than low memory consumption.

One possible idea is that rows can be merged if n-1 numbers (or group of numbers in the slot) are equal, e.g.,

    1 2 4
    1 2 5
    1 2 6
    1 3 4
    1 3 5
    1 3 6

can merge into

    1 2 456
    and
    1 3 456

which further can be merged to:

    1 23 456

and written as:

    {1} x {2,3} x {4,5,6}

My question is similar to https://stackoverflow.com/q/20890802/781723, but that one is limited to triples ($n=3$); I am interested in generalizing, where rows can be longer than 3.  I also found https://stackoverflow.com/q/46084505/781723, but that has no answer.


texts:
I'm a computer engineer and I've met hash functions theoretically speaking in "algorithms and data structure" and then in several applications (like databases, operating systems, computer architecture etc).

But I was wondering if there's some general theory about these functions and, specifically, if there's a general way to build such functions.


texts: Find a path in a complete graph with cost limit and max reward

texts:
I'm looking for an algorithm to solve this problem.

I have a region in which there are several areas identify by its id and x,y,z position. I've made a graph in which each vertex identifies one ot these areas (for a max of 200 vertex).
From a start point S, I know the cost, specified in seconds and inserted in the arch (so only integer values), to reach each vertex from each other vertex (a complete graph). When I visit a vertex I get a reward (float valiues).

My objective is to find a paths in a the graph that maximize the reward but I'm subject to a cost constraint on the paths. Indeed I have only limited minutes to complete the path (for example 600 seconds.)

The graph is made as matrix adjacency matrix for the cost and reward (but if is useful I can change the representation).

I can visit vertex more time but with one reward only!

I think to find the optimum solution is a np-hard problem, but also an approximate solution is apprecciated :D

Thanks

I'm trying study how to solve the problem with branch & bound...


texts: Is an inverse homomorphism always a homomorphism?

texts:
Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image $\delta$), is the inverse homomorphism $h^{-1}$ a homomorphism?

Since a homomorphism maps every symbol of the input alphabet to one word from the output alphabet, the inverse transformation to $h$ is a substitution $\sigma: \delta \mapsto \Sigma$ (which maps one symbol to a whole language - alphabet $\Sigma$).

What would be an inverse homomorphism to $h': a \mapsto \epsilon, \forall a \in \Sigma$ or would such a transformation even exist?

EDIT: The question should have rather stated: "Is there always an inverse homomorphism?" There obviously isn't since only isomorphisms have their inverse homomorphisms.


texts: If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

texts:
Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

what about $\cup$ and $\times$ operators? If $A \cup B$ or $A \times B$ is recursively enumerable is it true to say both $A$ and $B$ are R.E.?


texts: The relation between $BQP$ and $NP$ is an open problem, while it seems that $BQP$ is somewhat lower for $NP$ than the other way round. Is the status of lowness of these problems known?


texts: PRNG for generating numbers with n set bits exactly

texts:
I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < 64$ and return a pseudo-random 64-bit number with exactly $n$ bits set to $1$, and the rest set to 0.

My current approach involves something like this:

Generate a pseudorandom 64-bit number $k$.
Count the bits in $k$, storing the result in $b$.
If $b = n$, output $k$; otherwise go to 1.

This works, but it seems inelegant. Is there some kind of PRNG algorithm which can generate numbers with $n$ set bits more elegantly than this?


texts: Problem understanding Nilsson's general graph search and A* algorithm

texts:
I'm reading several books that present A* algorithm. More precisely, I'm Nilsson's "Artificial Intelligence a New Synthesis" and a textbook on problems of artificial intelligence which is written in spanish.

The following description of A* algorithm is from Nilsson:

I'm having some trouble with step 6. It says:

  Expand node n, generating the set M of its successors that are not
  already ancestors of n in G

To put you I context, G is the search graph while Tr would denote the search tree.

So, my question is: is this description of the algorithm right? In my opinion it should be instead:

  Expand node n, generating the set M of its successors that are not
  already ancestors of n in Tr

To help you understand my concern I show you one step of the algorithm as done in the other book:

In this picture the node that is going to be expanded is D. The dashed line shows that F is an ancestor of D in G. The black line to I says that I is an ancestor of D in the search tree Tr and of course in the search graph.

In this picture we see that when expand D we take into consideration F that was and ancestor of D in G (which contradicts Nilsson's step).

I hope I explained myself clearly. If you need any other details please just comment.


texts: What is the procedure for performing a binning analysis in Monte Carlo, or more generally, estimating autocorrelation times?

texts:
I'm working on a monte carlo project similar to the Ising model. I've found many examples on which I've based my code: https://github.com/danielsela42/MC_TBG_Model/blob/master/mc_project/mcproj_binned.py (my code).
From some papers I read on binning analysis, the errors after each binning step are supposed to converge. Mine ended up oscillating after some binning step. And so I'm getting negative auto correlation times.
I was hoping someone could either verify my procedure is correct, or explain a good procedure for dealing with correlated sampling.
Thank you in advance for the help!
This is my first time here. If this is not the right place to post this, where would be better?


texts: Proving that a BST with N>=1 nodes will have log(N+1) levels

texts:
I am trying to prove by induction  the following theorem:
Use Induction to prove the following fact: for every integer, $N\ge  1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels.
I've proved the base case but I am struggling to figure out how to apply induction to prove for the $K+1$ case. Any suggestions would be wonderful.


texts: I have just discovered the filed of data structure and I am fascinated by it. IS there an encyclopedia of data structures? Or at least do you know any recently constructed data structure that is not yet popular?


texts: An infinite decidable language that is a subset of $\overline { A_{TM}}$

texts:
What is an example of an infinite decidable language $L$, such that $L \subseteq \overline { A_{TM}}$ (which is known to be not Turing Recognizable)?

And of coures some evidence that L is indeed decidable and a subet as required


texts: Find the median of two sorted arrays of different size in O(min(log(n),log(m)) complexity

texts:
Given two sorted arrays of length m,n, how do I find the median of the union of these two arrays in O(min(log(n),log(m)) time?

I've been trying to come up with an algorithm (and a proof) for several days.
It's the same known question about finding the median of two sorted arrays but in  O(min(log(n),log(m)) time insted of O(logm+logn).
The arrays size may be different or equal (the solution should support both cases).

Here is the code I use:

int select(int *a, int *b, int sa, int sb, int k) {
    int ma = sa < k/2 ? sa - 1 : k/2 - 1;
    int mb = k - ma - 2;
    if (sa + sb < k)
        return -1;
    if (sa == 0)
        return b[k - 1];
    if (sb == 0)
        return a[k - 1];
    if (k == 1)
        return a[0] < b[0] ? a[0] : b[0];
    if (a[ma] == b[mb])
        return a[ma];
    if (a[ma] < b[mb])
        return select(a + ma + 1, b, sa - ma - 1, mb + 1, k - ma - 1);
    return select(a, b + mb + 1, ma + 1, sb - mb - 1, k - mb - 1);
}

/*
median:
uses select to find the median of the union of a and b (where a and b are sorted
positive integer arrays of sizes sa and sb respectively).
*/
int median(int *a, int *b, int sa, int sb) {
    int m1, m2;
    if ((sa + sb) % 2 == 1)
        return select(a, b, sa, sb, (sa + sb)/2 + 1);
    return select(a, b, sa, sb, (sa + sb)/2);

}

int main() {
    int a[3] = {2, 4, 6};
    int b[11] = {1, 3, 5, 7, 13, 17, 22, 23, 24, 25, 31};
    printf("\n median is %d\n", median(a, b, 3, 11));
    return 0;
}

However I'm not sure if this code solves the problem correctly in O(min(log(n),log(m)) time.  Is there a correct solution with this running time?


texts:
I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck.
Let me first describe it.

3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in it, one should determine if there exist an assignment that satisfies it.
Max-2-SAT: Given a CNF formula, where every clause in $\phi$ has exactly 2 literals in it, and a positive number $k$, one should determine if there exist an assignment that satisfies at least $k$ clauses.

Let me first show what I have tried so far.
Given $\varphi=\wedge _{i=1}^{n}C_i$ where: $C_i=(l_{i_1}\vee l_{i_2} \vee l_{i_3})$,
I set: $\phi=\wedge _{j=1}^{3n}D_i$, where: $D_i=(l_{i_1}\vee l_{i_2})\wedge(l_{i_1}\vee l_{i_3})\wedge(l_{i_2}\vee l_{i_3})$ and $k=2n$.
It's quite easy to see that this will not work...
Although, if there exist an assignment which satisfies $\varphi$ it means there exist an assignment that satisfies $k=2n$ clauses in $\phi$, the second direction is not true.
I found several reductions online (such as this, for example), but none of them were useful since in my problem, each clause in $\phi$ must have exactly two literals, where in the link above, the formula can also contain 1-length clause in it.
I could really use some help here.


texts: Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

texts:
There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight.

Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the total cost of the min-spanning tree of the selected $k$ vertices will be highest?

In my case, $n$ is around 1000, and $k$ around 100.


texts:
Let $\chi$ be an instance space and $H \in \{0, 1\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z_x\colon H \rightarrow \{0, 1\}$ s.t. $z_x(h) = h(x), \forall h \in H$.
Let $Z = \{z_x:H\rightarrow\{0,1\}\mid x\in\chi\}$. Is $\mathit{VCdim}(Z)<2^{\mathit{VCdim}(H)+1}$?

The only thing that comes to mind when seeing this is the Sauer lemma, but that's related to the growth function and I don't see how to apply it here. Anyone got any idea on how to approach this?


texts: how to find a node that is known to everyone but doesn't know anyone?

texts:
Problem I am trying to solve is this:

There are n nodes, and for every pair of node $X$ and $Y$,
the relation "$X \space  knows \space Y$" is either $T$ or $F$. It is possible that "$X \space knows \space Y$" but "$Y \space doesn't \space know \space X$".

We are trying to find if a special node exists: that is known to everyone but doesn't know anyone.
How can you find out if such node exists by using only this type of query:
For any nodes $X$ and $Y$, ask $X$ "$if \space X \space knows \space Y$". This query can be asked unlimited amount of times,
but the total number of queries should be $O(n)$.
I can think of $O(n^2)$ case but how to do it with $O(n)$ queries?
Thanks!


texts: Random file access in a block based file format

texts:
I am writing a program to store, retrieve and delete "blocks" of data of varying sizes.

The way it currently works is by keeping a database storing the locations of the blocks and the locations of free space in the file.

The file is split into pages such that in each page there are no two free chunk spaces next to each other (During a delete operation, any free chunks which are adjacent are merged into one bigger chunk)

The problem with this is that I am seeing horrible IO performance when removing a bunch of blocks and inserting new ones of different sizes (blocks range from 1k to about 200k and may be written anywhere in the file provided they fit in an existing free chunk in the file. If no such free chunk is found, a new page is created at the end of the file).

Can anyone suggest a way to improve on this, or maybe point me in the right direction?


texts: Reccurence of recursive function with unequal sizes of subproblems

texts:
Given pseudocode:

X is an array

function FUN(X)
    l = length(X)
    if l <= 1 then
        PRINT("Hello")
        return
    end if
    p = l / 3
    FUN(X[1...p])
    FUN(X[(l-p+1)...l])
end function

I now want to get the reccurence of this pseudocode. At the moment I have $$T(n) = 2 \cdot T(\frac{n}{b})\cdot O(1)$$

but the problem is that I don't know how to handle the fact that the first recursive call has a subproblem size of $\frac{1}{3}$ and the second has a subproblem size of $\frac{2}{3}$. What is $\frac{n}{b}$ then?


texts: Why doesn't playing audio stop other tasks?

texts:
If processors can only execute one thing at a time, how come I can play music continuously and still be able to run other tasks?

I understand the interrupt system, but isn't it needed that CPU continuously process audio for it to not sound jittery/laggy?

I am asking about the underlying implementation, is this question related to multi-threading? How does a 1-core, 1-threaded CPU be able to achieve this multitasking?


texts: Why aren't there computers with a base different than 2?

texts: Wouldn't non-digital computers, those that use a base higher than 2, be faster and more efficient? Especially with Moore's law reaching its limit, wouldn't circuits that have three, four or five states have advantages? Are there computers like that?


texts: In any complicated system, there is always some scope for error. When I program on my computer, the system computes perfectly each time. 1+1 always turns out to be 2. We take reliability of the computer almost for granted. What gives modern computers it's reliability? Are there no errors in computation, or errors, if any, are corrected by some means?


texts: Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p

texts:
I am trying to get my head around the Pumping Lemma to prove a language is non-regular.
I am reading the Sipser text book and he gives the following example.
Let B be the language $\{0^n 1^n | n \ge 0\}$
Let $s = 0^p 1^p$
I understand that the idea is you can split this string into xyz such that y can be pumped. It is the constraint of $|xy| \le p$ that is confusing me.
Sipser notes that due to this constraint y could not equal 01 nor could it equal 1. Why would y equaling either of those values violate the given constraint.
I am generally quite confused by the Pumping Lemma so any general advice or good resources you can recommend, I would appreciate.
Thanks!


texts: If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

texts:
The smallest grammar problem is to find a single-string CFG.  So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each respective sample, compute an approximate smallest CFG for the language?

I want to make a parser generator that automatically detects a grammar given some samples of programming languages.


texts: Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?

texts:
Reference Question from Forouzon Book Computer Network.
Find the status of the following generator related to two isolated, single-bit errors.
$$x^{15} + x^{14} + 1$$
Answer given :
This polynomial cannot divide any error of type $x^t + 1$ if t is less than 32,768. This means
that a codeword with two isolated errors that are next to each other or up to 32,768 bits
apart can be detected by this generator.
Can some one please help me why is this true...? Or even how should I have an in general approach to analyze such questions...?
(Sorry if this is very silly, but I am unable to get a grasp of how the reason works...!)


texts: Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

texts:
McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960).

From Wikipedia:

  In his 1967 Computation: Finite and Infinite Machines, Marvin Minsky
  in his § 10.6 Conditional Expressions: The McCarthy Formalism
  describes the "formalism" as follows:

  "Practical computer languages do not lend themselves to formal
  mathematical treatment--they are not designed to make it easy to prove
  theorems about the procedures they describe. In a paper by McCarthy
  [1963] we find a formalism that enhances the practical aspect of the
  recursive-function concept, while preserving and improving its
  mathematical clarity.

  McCarthy introduces "conditional expressions"
  of the form
  f = (if p1 then e1 else e2) where the ei are expressions
  and p1 is a statement (or equation) that may be true or false. This
  expression means: See if p1 is true; if so the value of f is given by
  e1. IF p1 is false, the value of f is given by e2. [...]

  The McCarthy formalism is like the general recursive (Kleene) system,
  in being based on some basic functions, composition, and equality, but
  with the conditional expression alone replacing both the
  primitive-recursive scheme and the minimization operator." (Minsky
  1967:192-193)

I'm interested in chronology. Was there any other formalism regarding recursive function before McCarthy Formalism (in computer science)?


texts: Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

texts:
I always considered Symmetric TSP to be inapproximable in general, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (which can be Symmetric or Asymmetric), which is approximable (e.g. Christofides algorithm).
However, I'm having doubts after finding the following paper :
An improved approximation algorithm for ATSP
Vera Traub, Jens Vygen (https://arxiv.org/pdf/1912.00670.pdf)
In their paper, there is no mention of Metric TSP, or the triangle inequality. Does this mean that I'm misunderstanding, i.e. Asymmetric TSP is in fact approximable, even without the triangle inequality?
EDIT : As Discrete Lizard pointed out, Metric TSP seems to not just imply (any) TSP respecting the triangle inequality, but rather Symmetric TSP respecting the triangle inequality. This does not change my last question though, and Yuval Filmus' answer is still correct.


texts:
I have on a few occasions trained neural networks (back propagation networks) with some rather complicated data sets (backgammon positions and OCR). When doing this, it seems that a lot of the work involves trying out different configurations of the networks, in order to find the optimal configuration for learning. Often there is a compromise between small nets that are faster to use/learn, and bigger nets, that are able to represent more knowledge.

Then I wonder if it could be possible to make some networks that are both fast and big. I'm thinking that at network where every neuron ain't fully connected ought to be faster to calculate than nets with full connection on all layers. It could be the training that detected that certain inputs are not needed by certain neurons, and therefore remove those connections. In the same way the training could also involve adding new neurons if some neurons seems to be "overloaded".

Is this something that have been tried out with any success ? Does any classes of networks exists with this kind of behavior ?


texts: Proof that truncation of a regular language is regular

texts:
Let $L_1$ be a regular language and $L_2$ any language.  I want to prove that the language of $L_1$ truncated by $L_2$ is a regular language, i.e.
$$\{w| wx\in L_1 \text{ and } x\in  L_2\}$$
is regular.
To prove that something is regular it is enough to prove that it is described by a regular expression.  We know that $L_1$ is described by a regular expression, but regular expressions don't handle "differences" in any obvious way.
We could imagine the DFA which accepts exactly the strings of $L_1$.  But to truncate the strings of $L_2$ we would need some way of recognizing the portions of the tail of the word which are in $L_2$ and there may be no DFA which does this.  Likewise for any recognizing DFA.
In general it's hard to imagine having "any language" interact with a regular language to produce a regular language.  The "any language" isn't constrained by any of the tools that seem relevant to regular languages, like NFAs and regular expressions.


texts: How to work out if an IEEE 754 floating point number is normalized?

texts: How do I tell whether a particular IEEE 754 floating point number is a normalized floating point number?  Is there some way to recognize an IEEE 754 normalized floating point number?


texts:
In a recent IT class we got the task of creating a finite state automaton that accepts only the words "auto" "automarke" "tomaten" and "automaten" and no others. Basically the whole class had no problems finding a 17 state solution, except for the guy two seats next to me who is incredibly convinced that its possible in 14, without justification. The front row failed trying to prove mathematically and logically why you need at least 17 states to do this, and now I am quite interested in the following question:

How would you go about proving the minimum number of states for this specific automaton, or any general automaton?

P.S. I can show my 17 state solution if requested

P.P.S I was redirected here from tcs.se


texts:
Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.

You start your travel at a given node, say $1$, and end your travel at a given node, say $12$. Your travel has $T$ time steps. At time step $t=1$ you must visit one of nodes $\{1,7,4\}$, at time step $t=2$ you must visit one of the nodes $\{7,3,45,9\}$, and so on. In other words, at a given time step, you are given a set with at minimum $1$ and at maximum $K\leq N$ nodes. Choose the nodes for all time steps such that the cumulative distance is minimized.

Am I correct, that such problem is NP hard? Given $T$ time steps and that at most $K$ nodes are possible at each time step, the complexity would be $O(K^T)$, right?

What algorithms could be applicable or useful for such a problem? In my scenario, $T$ can be very large (up to 20,000) but $K$ is rather low (10 on average, at most 100).

(Edit) - I encountered the problem in a diary of a traveller. For example, you know that a traveller started his journey at some location. For every journey entry, besides the raw text, the writer in the title writes a date  and a location name.

The problem is there often exist several different coordinates for a location name (i.e., multiple locations exists with the same name). An (I think reasonable) assumption I have come to, is that the shortest possible path (from start to finish) should approximate the travelled route quite well. I have a data set of multiple travellers with diaries like this and want to plot the routes onto a map (and hope to display a travelled route approximately in the way which in it was really travelled).

I have not yet come up with any good and general solution (besides brute-force computing the distance of every possible route, which may be impossible because there exist tons of diary entries and so many location names have multiple possible coordinates).


texts: If f(n) = Ω(n) and g(n) = O(f(n)), what do we know about g?

texts:
Let f(n) = Ω(n),
and g(n) = O(f(n)).Then g(n) = _______.

I thought of it this way, since f(n) is Ω(n),then f(n) belongs to the set of functions defined by Ω(n), ie,{n,$n^2$,$n^3$ ....}.  So g(n) will change accordingly , ie , g(n) will be of complexity O(n),O($n^2$),O($n^3$) ...etc. Is it correct to directly substitute functional values into O(f(n)) to get a sense of the complexity?


texts: Intuition why NP $\subsetneq$ EXPTIME would hold?

texts:
We know that P $\subsetneq$ EXPTIME, and that P $\subseteq$ NP $\subseteq$ EXPTIME.

I hear alot about the P = NP question and why it would intuitively be weird if it holds true, but I don't hear about the intuition behind why people think that NP $\subsetneq$ EXPTIME.

Are there intuitive reasons to assume that NP = EXPTIME or not? Why would we think one way or the other?


texts:
I (will, at the end) have a connected, undirected graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph , which has 3 nodes and 3 edges, iteratively. Every node added onto the graph and has 2 connections with the existing nodes (not necessarily with the initial 3 only) in the graph. When all nodes are added to the graph (N-3 nodes added in total), the final graph is constructed.

I'm asked, what is the maximum number of nodes in this graph that can be visited exactly once (except for the initial node), i.e., what is the maximum number of nodes contained in the largest Hamiltonian path of the given graph. (Okay, saying largest Hamiltonian path is not a valid phrase, but considering the question's nature, I need to find a max. number of nodes that are visited once and the trip ends at the initial node. I thought it can be considered as a sub-graph which is Hamiltonian, and consists max. number of nodes, thus largest possible Hamiltonian path).

I tried to apply Ore's Theorem but even for a small example graph, the Ore's Theorem might not be sufficient to tell if the graph is Hamiltonian even though it strikes you directly that it is Hamiltonian.

I thought I might use BFS since It's used to detect cycles in a graph: I needed to find the largest cycle which contained all the nodes in that cycle but given a large number of nodes, this approach might be slow and not desirable in my case since the timing will be crucial. For now this option is the last option if I can't come up with a solution.

After some thinking, I thought whatever the number of nodes will be, the graph seems to be Hamiltonian due to node addition criteria. The problem is I can't be sure and I can't prove it. Does adding nodes in that fashion, i.e. adding new nodes with 2 edges which connect the added node to the existing nodes, alter the Hamiltonian property of the graph? If it doesn't alter the Hamiltonian property, how so? If it does alter, again, how so?
Thanks.

EDIT

I, again, realized that building the graph the way I described might alter the Hamiltonian property. Consider an input given as follows:

1 3
2 3
1 5
1 3

these input says that 4th node is connected to node 1 and node 3, 5th to node 2 and node 3 . . .

4th and 7th node are connected to the same nodes, thus lowering the maximum number of nodes that can be visited exactly once, by 1. If i detect these collisions (including an input such as 3 3) and lower the maximum number of nodes, starting from N, I believe I can get the right result.

See, I do not choose the connections, they are given to me and I have to find the max. number of nodes.

I think counting the same connections while building the graph and subtracting it from N will give the right result? Can you confirm this or is there a flaw with this?


texts: Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant

texts:
Given a directed weighted graph, is there an algorithm that does the following:

Removes as many edges possible.
Reduces as many weights as possible.

Given the constraint that the net weight of all edges connected to the vertex (sum of incoming edge weights minus sum of outgoing edge weights) remains the same and every edge weight remains non-negative.

Examples:

The graph "A -10-> B -10-> C" could be reduced to "A-10->C" since vertex B has net zero weights (10 incoming and 10 outgoing)

The graph "A -10-> B -3-> A" could be reduced to "A-7->B".

Thanks.


texts: How to determine whether a dependent type that doesn't fit the monad instance is categorically a monad

texts:
[Using Idris syntax and terminology, but the question is not about Idris]

If a monad interface (or type class) has a constraint requiring applicative functor, a monad instance can be written by implementing either bind: (>>=) : Monad m => m a -> (a -> m b) -> m b, or join : Monad m => m (m a) -> m a, or both. However, this is a much more constrained and specific type of monad than the general concept of monad in category theory.

In a dependently typed language, it is not uncommon to stick some kind of size into the type in order to allow the typechecker to recognize well-founded recursion, etc. The unfortunate impact is that because bind and join may not be size-preserving operations, you can loose your monad instance, and thus not be able to use whatever syntactic sugar the language may provide, etc. That's okay though; let's set that aside. What I'm wondering more fundamentally is if you've only lost your instance of Monad, or if your type has actually stopped being a monad. If you have a type k : Nat -> Type -> Type, might not pure : a -> k n a and (>>=) : k n a -> (a -> k m b) -> k (op n m) b / join : k n (k m a) -> k (op n m) a still satisfy the conditions to be a monad for some op : Nat -> Nat -> Nat, e.g. +?

I'll give a specific example: a freer monad indexed by size in order to allow for total operations.

||| http://okmij.org/ftp/Computation/free-monad.html
module Freer

%default total
%access public export

data FFree : (Type -> Type) -> Nat -> Type -> Type where
  FPure   : a -> FFree g n a
  FImpure : g x -> (x -> FFree g n a) -> FFree g (S n) a

Functor (FFree g n) where
  map f (FPure x)     = FPure (f x)
  map f (FImpure u q) = FImpure u (map f . q)

pure : a -> FFree g n a
pure = FPure

promote : {m : Nat} -> FFree g n a -> FFree g (n + m) a
promote (FPure x)     = FPure x
promote (FImpure u q) = FImpure u (promote . q)

assocS : (m : Nat) -> (n : Nat) -> m + S n = S (m + n)
assocS Z n = Refl
assocS (S m) n = cong $ assocS m n

apply : FFree g n (a -> b) -> FFree g m a -> FFree g (m + n) b
apply {n} {m} (FPure f) x =
  promote $ map f x
apply {n=S n} {m} (FImpure u q) x =
  let y = flip apply x . q
  in rewrite assocS m n in FImpure u y

bind : (a -> FFree g n b) -> FFree g m a -> FFree g (n + m) b
bind {n} {m} f (FPure x) = promote $ f x
bind {n} {m=S m} f (FImpure u f') =
  let y = bind f . f'
  in rewrite assocS n m in FImpure u y

join : FFree g m (FFree g n a) -> FFree g (n + m) a
join = bind id

This allow my monad methods to be total for my freer monad. But... is it still a valid monad? I do not see why adding some typelevel information would stop it from being one; other than some typelevel fanciness in the form of rewrite ... in ... etc. the method implementations are the same as those given in the "Freer Monads, More Extensible Effects" paper. However, I am used to seeing the monad laws written in terms of Monad, which I am no longer able to implement here since e.g. Free g 3 ≠ Free g 2.

How do I prove or disprove that, Monad interface and syntactic sugar aside, I still have a monad here?


texts: Compute context free grammars for twice the amount

texts:
$$\{ a^{k}b^{j} : k = 2j , k \geq 0\}$$

I'm trying to wrap my head around CFG's but I am having trouble. From this language, there should be twice as many a's than b's. Here is my attempt.

$$S \to aSb \ | \ a Sa \ | \ \epsilon $$

$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSabb \Rightarrow aaaabb $$

But, I can also have this arise, which I don't want:
$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb $$

How can I force the CFG to put twice as many a's as b's? Is there any general approach to solving these?


texts: Are all terms of type forall a. a operationally bottom?

texts:
Is there a proof that all terms of type $\forall{a}. a$ are operationally $\bot$, in a non-weakly-normalising version of System F?

If you ask a free theorem calculator such as this one for the free theorem of $\forall{a}. a$ (written just $a$, as the tool adds implicit $\forall$s for each free type variable), you get the rather unhelpful

forall t1,t2 in TYPES, R in REL(t1,t2). (f_{t1}, f_{t2}) in R

Which seems to me only to imply that instantiations of $f$ at any two types are related by any relation.

Does this imply that $f$ must be a looping term?


texts: What is an example of meta-heuristic algorithm for solving Mario NP-hard problem?

texts: Applying entertainment with computations is my main motivation in studying Computer Science, however, I'm still a neophyte to this field. While searching across the net, I came across this paper Classic Nintendo Games are (Computationally) Hard, indicating that Mario is an NP-Hard problem. Given by the proof of NP-hardness in the paper, I'm wondering, can we apply metaheuristic algorithms in solving the Mario Problem? If yes, I would be glad if you can provide an example and show how it works.


texts:
I came across the following dynamic subtraction game:

  There is one pile of n chips. The ﬁrst player to move may remove as many chips as
  desired, at least one chip but not the whole pile. Thereafter, the players alternate moving,
  each player not being allowed to remove more chips than his opponent took on the previous
  move. What is an optimal move for the ﬁrst player if n = 44? For what values of n does
  the second player have a win?

Now, I know how to solve basic subtraction games, i.e., when both the players are allowed the same set of moves throughout the game (e.g., subtract only 1, 2, or 3 throughout the game). But in the game mentioned above, this set of possible numbers for subtraction is not fixed. I have no clue how to go about solving this question. Any kind of help would be appreciated.


texts: Instruction Set Architecture (ISA) design

texts:
Yes, this is a homework question, I've tried working it out and was hoping I could get pointed in the right direction.
Here's the question:
You are designing the instruction set for a new type of computer. The
computer has 64 instructions, 16 general-purpose registers. It supports a
byte-addressable memory of up-to 32MB. Answer the following question:
a. For a 3-operand ADD instruction that only uses register addressing
mode, how long (number of bits) should the instruction be?
b. For a 2-operand ADD instruction, in which one of the operands is a
memory location with direct addressing mode, how long (number of
bits) should the instruction be?

I know the question's been asked recently but both questions and answers weren't helpful.
I know that with 64 instructions and 16 registers, there must be 4 bits per register.  I don't exactly know the usage for the 32MB memory right now.
A similar example of part (a) exists on Wikipedia, where it states 4 instructions are needed for a 3-operand register addressing mode (load reg1 into a load reg2 into b, add reg1 and reg2 to reg3, store reg3 in c).  Because it mentions 4 instructions, I thought that would be 1 bit, but that's a really small amount.  There are 3 registers used in the instruction, which would be 12 bits.
For part (b), I believe one is a memory location with a direct addressing mode (as stated) and the other is like part (a), using register addressing mode.  There are only two operands, but only one is using register addressing mode, meaning only one register is used?  In that case, the length of the instruction should be 4 bits.
I would appreciate any help! If I'm misunderstanding some of the terms please let me know! Thanks!


texts: Compute 'insertable' letters in a regular language

texts:
Let $L$ a regular language and define the subsequence closure of $L$ as

$\qquad \displaystyle S(L) = \{ w \mid \exists w' \in L.\ w \text{ subsequence of } w'\}$.

The problem I want to solve is to find for such subsequences $w \in S(L)$ which letters can be inserted into them so that the result is also in $S(L)$. Formally:

  Given $w_1\dots w_n \in S(L)$, output all pairs $(i,a) \in \{0,\dots,n\} \times \Sigma$ for which $w_1 \dots w_{i} a w_{i+1} \dots w_n \in S(L)$.

Consider, for instance, the language$\{ab, abc, abcc\}$. The string $b$ is in $S(L)$ and inserting $a$ at the beginning -- corresponding to $(0,a)$ -- yields $ab \in S(L)$. On the other hand, the string $cb$ is not in $S(L)$; there is no way to convert it to a language string by insertion.

Using this language, if the input string is $b$ the possible insertions I am looking for are $(0,a)$ and $(1,c)$ at the end. If the input string is $bc$ the possible insertions are $(0,a), (1,c)$ and $(2,c)$.

The use of this algorithm is in a user interface: the user builds strings belonging to the language starting from an empty string and adding one character at a time in different positions. At each step the UI prompts the user with all the possible valid letters in all the possible insertion positions.

I have a working naive algorithm that involves a lot of back-tracking, and it is way too slow even in relatively simple cases. I was wondering if there is something better, or -- failing that -- if there are any available studies of this problem.


texts: Online Learning Resources for Discrete Mathematics

texts: Are there any good Discrete mathematics learning web resources with problem sets?


texts: Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor?

texts:
I'm not nearly at the experience level in computer science to be able to properly determine the number of instructions involved in basic ALU calculations, and I'm interested in a certain software concept where the difference is important.

Multiplication

       1011   (this is 11 in decimal)
     x 1110   (this is 14 in decimal)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is 154 in decimal)

I've been studying the binary multiplier, which seems to calculate partial products with binary, and then shifts them to the left, the very same way that we do with base-10 multiplication in grade school. It would seem to me that this would require 2 instructions per digit, but that's merely a barely-educated guess.

Addition

I've found Wiki's explanation of an adder-subtractor to be far more advanced, (in description, not operation, surely), and I've had less luck interpreting it thus far.

Purpose

My goal is to determine the number of instructions required to compute the addition / multiplication (respectively) of number sets. Basically, I want to figure:

5 x 5 = 10 --> 5 instructions //example
5,000,000,001 x 456892 --> 50 instructions //example

1 + 1 = 2 --> 4 instructions //example
1,000,042,569 + 1,491 = 1,000,044,060 --> 45 instructions //example

Tl;dr - My Question:

Is it possible to accurately determine the number of instructions required to multiply or add two (whole number) integers in a modern processor?
If so, how is this figured (in both addition and multiplication, based on the size of the number)?


texts:
I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \{a, b\}$.

When I implement this graph in JFLAP, I'm receiving an error that there are transitions out of final states. Is it OK to construct a transition graph like this, or is it considered bad practice? If so, can you help me understand the correct way to construct the transition graph?


texts: Compute hash value according to multiplication method

texts:
In "Introduction to Algorithms" by C. E. Leiserson, R. L. Rivest and C. Stein (ISBN:  978-0262033848), p. 264 they state this:

I get everything but the last part stating $h(k) = 67$

>>> r = 17612864
>>> bin(r) # r's binary representation
'0b1000011001100000001000000'
>>> int(bin(r)[: 14 + 2], 2) # extract 14 most significant bits and convert to int
8600


texts:
I am trying to understand the asymptotics of

\begin{equation}
f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})}
\end{equation}
In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?


texts: If we sort a table column-wise and then row-wise why the table is still sorted column-wise?

texts:
Say we have a $n \times n$ table which elements are sorted column-wise, for example:

$$
\left( \begin{array}{ccc}
2 & 4 & 1 \\
3 & 5 & 6 \\
7 & 9 & 8 \end{array} \right)
$$

I would like to prove that if we sort this table row-wise, it will be still sorted column-wise.

This is one of the steps to prove the shell sort correctness.


texts: $a^{2n}$ where $n\geq1$ is not Regular using Pumping Lemma

texts:
I'm having trouble understanding Pumping Lemma for $RL$ , i know that $0^{2n}$ is regular and we can design a FSM for it.Here's my pumping Lemma statement

Let $p$ be the pumping length and my string is $0^{2p}$
1. $z=|0^{2p}|=> 2p > p $ (Satisfied)
2. $z=uvw$ such that $|uv|\geq p$, I'm choosing $|u|=n-p$ and $|v|=p$ so that $|uv|\geq p$ (Satisfied)
3.Now $u(v^i)w$, I choose $i=3$ then $|uvw|=2(n+p)$ which is even
But if $n=2$ then $|uvw|=2n+p$, how do i know if this could be even/odd?


texts:
Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$?

Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?


texts: Are references of any use without updating?

texts:
Almost all type-theoretical treatments of references that I've studied introduce references as accompanied with at least three operations (sometimes including the fourth):

Construction (allocation): $ \text{ref } e $
Elimination (dereferencing): $ !e $
Updating: $ e_1 := e_2 $
(not as common) Destruction (deallocation): $ \text{free } e $

My question is this: Would references be of any use without updating (construct #3 above)? If so, what would be a common use? Does the ability to use updates with references lend any more "power" to a language? You can answer assuming either the presence or absence of construct #4 above; if it affects your answer, please explain how.


texts: Prove that a model of infinite tapes is stronger then turing machine model

texts:
I want to prove that if we have a model, $A$, with unbound number of tapes, then
$A$ is stronger then Turing Machine model. Can you help me with example of such a language that $M$ will fail but $A$ will give an output? thanks.


texts: Fundamental idea of this memory denial of service simulation using array copy?

texts:
I am just watching this lecture Computer Organization - Introduction And Basics where
the lecturer mentions about using a simple code to demonstrate how memory denial of service can be simulated in DRAM by exploiting an optimzation DRAM Controller does internally. The optimization seems to be that DRAM Controller serves the same row buffer whenever possible for the instructions coming to the pipeline and so it can be exploited by sending instructions that use a very localized data giving it priority.

//initialize large arrays A and B

for(j=0; j<n; j++)
{
index = j*linesize;
A[index] = B[index]
}

I just wanted to understand the fundamental concept of this approach. The Lecturer says that the above code would copy an Array from B to A. However I am not sure how it actually would copy an Array from B to A because it doesn't seem to go over each index item.

My real doubt, assuming that this is just a simulation code which copies some part of B to A for demonstration purpose and that linesize is just a large value to make a cache miss, is if the central idea behind this something like:

a) chose an index that is sufficiently wide apart so that a       cache miss happens

b) yet the memory is close enough for it to be in the same row for the memory controller to serve from the same row buffer

Which is needed to simulate this DoS (denial of service) scenario?

Quoting from the paper that explains this in depth Memory Performance Attacks - Denial Of Service In Multi Core Systems

  The arrays in stream are sized such that they are much larger than the
  L2 cache on a core. Each array consists of 2.5M 128-byte elements. Stream (Figure 3(a)) has very high row-buffer locality since
  consecutive cache misses almost always access the same row (limited
  only by the size of the row-buffer).


texts: Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

texts:
I am trying to solve the following recurrence relation:
$$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$

I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$

I am trying to prove it using a recurrence tree.

The tree is not balanced. Particularly, the longest path from the root to a leaf is the leftmost one  with a length of $\log_2n$ when the shortest path is the rightmost one with a length of  $\log_3n$.

We get that at each level,except the first one, the cost is $< n$. In more detail,the first level has a cost of $n$. The nodes on the second level add to a $\frac{5}{6}\cdot n$ cost, the third level has a cost equal to $\left (\frac{5}{6}  \right )^2\cdot n$ and so on...

So, untill the height of $\log_3n$ we have a cost of $$n\sum_{i=0}^{\log_3n-1}\left (\frac{5}{6}   \right )^i = n\cdot \frac{\left (\frac{5}{6}\right)^{\log_3n}-1}{\left (\frac{5}{6}\right)-1}$$

So, the result above seems to be a lower bound for my function $T(n)$

Is my approach correct? If yes, then how do I go on in order to prove that the time complexity is $T(n)=Θ(n)$.Thanks in advance!


texts: How to find min or max in constant time using infinite # processors?

texts:
Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ability to perform concurrent writes

I have tried dividing up the numbers into groups of 2 each and then using $n/2$ processors at the first step and then $n/4$ processors on the output of the first step etc. I can't see how to make use of more than $n/2$ processors given that I have $\infty$ of them


texts: What will i obtain if i apply a xor-ing a one way function and it's input?

texts:
I know that a one-way function is informally a function that it's easy to compute but hard to invert.
If f(x) is a one way function the function  $g(x) = x\oplus f(x)$ is a one-way function?
My intuition is that it's but i not really sure.


texts: What is the complement of Halting Problem?

texts:
I understand that Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. That is, there are two options for HP: Halt (accept/reject) OR loop.

With this definition of HP, I am unable to understand what is co-HP, since any program can have only 2 options, Halt or loop, so what is co-HP? How do we even know co-HP exists?


texts: Closed walk in planar graphs that contains $k$ faces

texts:
Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$.

Output: A shortest closed walk (one among possibly many, if exists) in $G$ using $e$ and $f$ which contains exactly $k$ faces of $G$.

A walk $w = v_1,e_1,v_2,...,e_i,v_i$ (where $v_j \in V(G), e_j \in E(G)$ for $1 \le j \le i$) uses an edge $e$, if $e = e_j$ for some $1 \le j \le i$. Also a walk $w$ contains the face $g$ if in the embedding of $G$ on sphere when we consider $w$ and $g$ as closed $2$-dimensional polytopes, then $g \subseteq w$.  A walk is allowed to have repeated vertices/edges.

Can this problem be solved in polynomial time?


texts: Do data points mean Eigenfaces in higher dimensional space?

texts:
I saw the following animation at making sense of PCA
, which shows blue data points.

I am reading a paper on Eigenfaces which says that:

  "a typical image of size 256 by 256 becomes a vector of dimension
  65536 or equivalently a point in 65536 dimensional space"

The paper is available at the following link:
Eigenfaces for Recognition

My question is that in the context of Eigenfaces is each blue point an image?

Somebody please  guide me.

Zulfi.


texts: What are the mathematical prerequisites for adaptive machine learning algorithms?

texts: I am a PhD student in Computer Science who switched his PhD a little bit towards ML algorithms combined with something else... I am an expert in that something else, say image processing, but not an expert in Machine Learning. What should I read/learn to get the ML mathematics right? Especially for adaptive learning algorithms.


texts: Substring in a infinite sequence of numbers

texts:
I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers.

Example:

1234567891011121314151617181920 ...

S = 141

Result: 18

All i think about is convert sequence to string and find substring using Rabin-Karp or KMP. But i feel that i can use it as numbers and there is some O(1) solution using math.

Another thought is split S on pieces:

141 = [(1, 4, 1), (1, 41), (14, 1), (141)]

And i have (1-9)(10-99)(100-999)(1000-9999)... which represents infinite sequence.

Than i can use this algo:

For (1, 41): try to find 1 from (1-9) and what goes next, if 41 is not next number, than try next tuple.

For (14, 1): try to find 14 from (10-99) and and what goes next, if 1 than find position of '14'.

But i'm not sure that this is correct solution.
Maybe some advices?


texts:
I can see that we can do higher kinded types ( * -> *) -> * in Scala and Haskell and other languages. I'm looking for a simpler vanilla implementation of just the basic static type checking system - perhaps in Prolog or MiniKanren.

My question is: Is there an implementation of higher kinded types in typed lambda calculus?


texts: How to sample Bivariate Normal Distribution with Accept reject method

texts:
I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods:

Prior Sampling
Gibbs Sampling
Rejection Sampling

I have done the first two samplings and I also have clear understanding of what accept reject method or so-called rejection sampling is.
yet I can not find any proposal distribution for it.

Rejection Sampling and proposal distribution
assume you have a distribution $f(x)$ which is not easy for you to sample.
choose another distribution that is easy for you to sample wisely called $g(x)$ so that for some constant $C$ for all $x$ we have $C.g(x) > f(x)$.
we call this $g(x)$ the proposal distribution.
sample from $g(x)$ and name it $X_i$ as you chose $g(x)$ because it was easy to sample. accept this sample with a probability of $p = f(X_i)/C.g(X_i)$.
As I said before I cant find any $g(x)$ easy enough to sample and yet bigger than bivariate normal distribution for some $C$.


texts: Minimum set cover with incompatible sets

texts:
I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously).
To state it more formally:
We have a finite base set $X$ and a family $\mathcal{R}$ of subsets of $X$. We also have an undirected graph $G$ with vertex set $\mathcal{R}$ and edges representing incompatibilities between sets. The goal is to find a minimum set cover of $X$ which is also an independent set of $G$.
Does this problem have a name? Or is it a special case of a studied problem? Or can it be reduced to a well-studied problem with a small blowup in runtime? (by "small blowup" I mean not simply polynomial, but preferably a small degree polynomial).
I'm particularly interested in the geometric variant where $X$ is a set of points and the sets in $\mathcal{R}$ are defined as the intersection of $X$ with some simple geometric ranges (in which case tools such as VC-dimension, $\epsilon$-nets, range-searching and so on might come in handy for approximation algorithms). But I welcome any relevant reference.


texts: Solving NP problems : analogy between the SAT problem and the shortest path problem

texts:
in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences),

whose purpose is to show how a SAT problem can be solved as the shortest path problem would be,

I understand that

there are n path paterns as n different boolean variables belonging to an "AND group of clauses". "Clause" being "an OR group" composed of conditions over some of the n variables.
 example : of a SAT problem being "find values of x1, x2, x3 such that clause1 AND clause2 AND clause3 is true", with clause1 being x1 OR x2 (is true), clause2 being x1 OR NOT(x3), etc.
m added vertices to force the m clauses to be ensured while having an unique "local" shortest path (within a local pattern)

But the thing I don't understand is why each pattern has to have 3(m+1) vertices? Why 2 diamonds per pattern isn't sufficient ?

Thank you for enlighting me


texts: Providing Tight Example in Approximation Algorithm Analysis

texts:
Let's say I found  a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight.

Do I now need to come up with an example of generic size $n$ or does it suffice to show that I   have an example of size $10$ for which the algorithm yields $2OPT$?


texts: Minimal paths as solution of a linear program of a special network flow

texts:
Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$.
We're looking for the shortest s-t-path.

By regarding this problem as a special flow network, we can express this using linear programming as follows :

Minimize the function:
$$ \sum_{e\in E} c_e\cdot x_e $$

Under the constraints:
$$
\forall v\in V-\{s,t\}: \sum_{e\in in(v)}x_e -\sum_{e\in out(v)} x_e = 0
\\
\sum_{e\in out(s)} x_e = 1
\\
\sum_{e\in in(t)} x_e = 1
\\
\sum_{e\in in(s)} x_e = 0
\\
\sum_{e\in out(t)} x_e = 0
\\
\forall e\in E: x_e \ge 0
$$

Here $c_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

About the correctness:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$.

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$  is an  $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints.

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
 Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality:
$$1\cdot p_{min} \le \sum_{p\in M} \lambda_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda_p \ge 0 , \sum_{p\in M} \lambda_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.

My question now is: Did I miss something in the proof?

Addendum:

It turns out that the above proof needs that each $s-t$-path has a unique cost. Otherwise, there might be no single $s-t$-path with minimal costs. In this case,  it can't be shown that the solution $S$ only contains a single of those paths with minimal costs.
However, in this case, by the reasoning above, it still is true that every path in $S$ is optimal. So in this case, we can just pick any path in $S$ as solution (which we can find using e.g. DFS)

Some final (off-topic) remarks:
This whole procedure seems like a lot for a less efficient method to obtain a shortest path. What caught my eye were the following two properties of this algorithm:
$(i)$ Besides the non-negativity constraint, all constraints are actually equalities.
$(ii)$ The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)


texts:
I'm looking for a customer clustering solution. I have done a lot of research on the machine learning level to find algorithms that could fit my needs but I can't find much information when the data is mainly text.

I searched for clustering with string but found little relevant ( for me). Do you have any ideas for algorithms that could be used?

Type of relevant data :

user right
data
protocol


texts: prove: max (w(E), w(E)) is a 1/2 approximation to the value OPT

texts: Hey I would like to find a answer for b. for a  look to the picture that is my answer for it. But I dont habe any Idea how i can solve this. Thank you guys. (I had to translate it to english maybe it will be hard to understand it sorry about that).


texts: Is there any study or theory behind combining binary search and interpolation search?

texts:
I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files by date/time window.

Whilst doing this, I decided to try interpolation search (I didn't know that was what it was called, I kind of stumbled across the idea by myself). Then for some reason I continued to the idea of alternating interpolation steps with binary split steps: On step 0 I would interpolate to decide test point, then step 1 I would take the exact midpoint etc.

I then benchmarked the system using pure interpolation search, pure binary search and my combination attempt. The alternating approach was a clear winner, both in time and number of tests required before finding a set of randomly chosen times.

Inspired by the linked question, I just made a quick search for "alternating interpolation search and binary search" and found nothing. I also tried "hedged interpolation search" as suggested on my comment on one of the answers.

Have I stumbled across a known thing? Is there any theoretical justification for it being faster for certain types of data? The log files were typically large for the time (e.g. 1-2 GB of text with maybe 10 million rows to search), and the spread of dates/times in them was complex with heavy bursts of activity, general peak times and quiet times. My benchmark tests sampled from an even distribution of target times to find.


texts: How do you find all integers in a sorted array of size n that appear n/k times?

texts:
I try to find the solution to this problem:
How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time?
I could only find this question, where O(klogn) solution was provided.


texts: Feedback polynomial of 7-bit Linear Feedback Shift Register


texts: Min max solution to the random assignment problem

texts:
Consider the standard assignment problem: $n$ people are assigned to $n$ jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) distribution), it is known that the expected sum of costs is $\pi^2/6$ .
An alternative solution to the assignment problem is to choose an allocation that instead minimizes the largest costs incurred by any individual, in the spirit of the John Rawls fairness criteria (see here). Is it known any algorithm that finds such maximin allocation, and is it known what is the random sum of costs in the random version of the problem?
Many thanks,


texts: Decision tree and information-theoretic lower bound

texts:
Consider the following problem :

Consider the problem of finding the median of a three-element set {a, b, c}.
a. What is the information-theoretic lower bound for comparison-based
algorithms solving this problem?
b. Draw a decision tree for an algorithm solving this problem.

The answer of this problem is shown below :

My problem is with number a. According to my understanding  the information theoretic lower bound = ceil (log2(2!)) , so in this question it should be equal to ceil (log2(6)) =3 because here we have 6 leaves not 3 ?


texts:
When I see a problem like "Write a grammar for a language $L$ if $L = \{..\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise:

  Let $L$ a language which alphabet is $\{x,y,z\}$ and accepts strings
  $w$ where there aren't consecutive $x$'s nor consecutive $y$'s nor
  consecutive $z$'s.

My first aproaching was to stablish that $x$, $y$ and $z$ each one are in $L$, that is:

$$S \rightarrow x \mid y \mid z$$

If the string has an $x$, there can be a consecutive $y$ or $z$, similarly for the other symbols. I assume that there are productions $A$, $B$ and $C$ that make the work, so the start production is:

$$S \rightarrow xA\mid yB\mid zC\mid x\mid y\mid z$$

Therefore $S$ can be splitted to define $A$, $B$ and $C$:

$\begin{eqnarray*}S &\rightarrow& A \mid  B \mid  C \\A &\rightarrow&  yB \mid  zC \mid  y \mid  z \\ B &\rightarrow&  xA \mid  zC \mid  x \mid  z\\ C &\rightarrow&  xA \mid  yB \mid  x \mid  y \end{eqnarray*}$

But as you all can see this is just my version, I started with base strings accepted by $L$ and then I followed my own thought of how to build the grammar. Is there a easy way to do this? or some advice for similar languages? (like those which have different number of symbols).


texts:
Show that the following language is NP-complete
  $$ L = \{ \langle G,k \rangle \mid \text{$G$ is a graph with a set $S$ of $k$ vertices hitting every edge of $G$}\}. $$

I know I should reduce the problem to SAT. But how I can do it?


texts: How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?

texts:
I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when you add the Kleene Star *, Kleene Plus +, and question mark ? to that grammar, commonly seen in regular expressions.

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

Say the grammar is like this:

S -> A+
A -> BX?
B -> a+ // letters
X -> ! // exclamation

How do you convert this to Chomsky Normal Form, given that it uses *, +, and ?? In particular, I am wondering what the general pattern is to convert the Kleene Star/Plus and question mark to CNF, not necessarily how to do it in this example, but whichever is easiest to demonstrate.

Is it something like this?

// first step
S -> A+
A -> BX?
B -> a+
X -> !

// replace + with *
S -> AA*
A -> BX | B
B -> aa*
X -> !

// replace * with new rules and ɛ
S -> AI
I -> A | ɛ
A -> BX | B
B -> aJ
J -> a | ɛ
X -> !

// replace X -> aY with X -> ZY and Z -> a
S -> AI
I -> A | E
A -> BX | B
B -> KJ
J -> K | E
X -> !
K -> a
E -> ɛ

I am just guessing here, not sure how it is typically done. Also, from the few resources I have found, it sounds like you are supposed to also remove the epsilon rules somehow. There doesn't seem to be many thorough online resources demonstrating this though, any book recommendations?


texts:
Prove that $(L^R)^* = (L^*)^R$ for all languages $L$.

My attempt: Suppose $w \in (L^R)^*$. So, $w = w_1\dots w_l$, for some $w_1, \dots , w_l \in L^R$. Since $w^R \in L$, then $w^R = w_l\dots w_1$, for some $w_l, \dots , w_1 \in L^*$. Therefore, $(L^R)^* \subseteq (L^*)^R$.
Honestly, I don't know how to proceed onwards, because this part doesn't sound right. I feel like I messed up with those symbols as this topic is really abstract. Any help? Thanks in advance.


texts: Proving that the reversal of a language reversal is that language

texts:
I am trying to prove that with language L, (L^R) ^R =L
So that the reversal of the reversal of the language is the original language L.

I have proved that before with a string not language (let's call it a string 's').

(s^R)^R = s.
Proof by induction on the length of s.

Base: |s|=0. s=ε. (s^R)^R =(ε^R)^R =(ε)^R =ε=w.
Induction hypothesis: if 0 ≤ |x| ≤ n, then (x^R)^R = x.
Induction step: Suppose |s| = n + 1. Then we can write s = xa, where a is a symbol and 0≤|x|≤n. Then
(s^R)^R
= ((xa)^R)^R since s = xa
= (ax^R)^R since (xy)^R = y^R*x^R (think of a as a string of length 1) = (x^R)^R*a^R same as previous line but using outer R
= (x^R)^R*a using the second part of the definition of reverse with u=ε.
= xa by the induction hypothesis
= s since s = xa

How can this reasoning the expanded to Languages? In essence I am proving the same operation, but I am dealing with languages instead of strings. Languages are made up of strings. Thoughts?


texts: Could someone check my recursive program correctness proof that returns $F(x, y) \rightarrow x + y$?

texts:
For $k \in \mathbb N$, we define $Q(k)$ as follows:

$Q(k): $ let $x, y \in \mathbb N$ and $x$ is a multiple of $3$ and $k = x + y$, then $FUN(x, y)$ terminates and returns $x + y$

I will prove $Q(k)$ using induction

Base Case: let $k = 0 \to iff (x = 0, y = 0)$

By line 1, 2, 5, $FUN(x, y)$ terminates and returns $0 + 0 = x + y$ as wanted

Inductive step: Let $k > 0$. Suppose $Q(j)$ holds whenever $0 \leq j < k$ [I.H]

What to prove: $Q(k)$ holds

Since $k > 0$, it follows that line 3-7 could run since line 1 is not satisfied.

Therefore two cases: $y > 0$ and $y \leq 0$

Case 1: If $y > 0$, then line 3, 4, and 7 will run.

Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x+3, y - 1)$

By IH, $FUN(x+3, y - 1)$ terminates and returns $x + 3 + y - 1$

By line 3, 4 and 7. $FUN(x, y)$ terminates and returns $x + 3 + y - 1 - 2 = x + y$ by algebra, and as wanted

Case 2: If $y \leq 0$, then line 5, 6, and 7 will run since line 1, 3 are not satisfied

Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x - 3, y )$

By IH, $FUN(x - 3, y )$ terminates and returns $x - 3 + y$

By line 5, 6 and 7. $FUN(x, y)$ terminates and returns $x - 3 + y + 3 = x + y$ by algebra, and as wanted

Therefore $Q(k)$ holds as wanted

This is my attempt above, not sure if I'm correct. I'm pretty confused on how to use IH in this or if my input size is even good. Is it correct?


texts: Computing 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time

texts:
I've constructed an algorithm that solves the 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time. I'm new to algorithms and was wondering how good is my running time? Googling didn't help.
thanks..


texts: Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$

texts:
I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$.  I think it should be something like this
\begin{align*}
S &\to aA \mid a\\
aA&\to aaaA \mid aa
\end{align*}


texts: If the parent in a bridge is the root, is it a bridge cut node?

texts:
I am going through Professor Skiena's textbook and he says that there are 3 types of cut-nodes - root, bridge cut node, and parent cut node.

Now if the earliest reachable ancestor from a node is itself, it's parent and the node (if not leaf) become bridge cut nodes.

My question is that we have a simple 2-node undirected graph -> A --- B.

In this case, B's earliest reachable ancestor is B itself and hence A becomes the bridge cut node. However, I am unsure that should be the case; since if I delete A, even then B exists and the num_components = 1?


texts:
Prove that the number of circuits with bounded fan-in (of 2) of size $s$ is at most $s^{O(s)}$.
Give the best explicit bound you can get.

I know that for a circuit of size $s$ in order to generate a string to represent it I need for every edge, which I have at most $s$ of those, to represent from which vertex it start and in which vertex it ends and for that I need $2s \log s$ bits.
In addition I need another 2 bit for every vertex to mark whether it is an input, an OR/AND/NOT Gate.
So overall I need $O(s \log s)$ bits to represent a circuit, and there are $2^{O(s \log s)} = s^{O(s)}$ circuits like that.
Am I in the right direction or am I missing something? And is $2^{3(s \log s)} = 8s^{O(s)}$ the bound?


texts: Is there an efficient algorithm for expression equivalence?

texts:
e.g. $xy+x+y=x+y(x+1)$ ?

The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or division.  Letters are variables.

If it helps, we can forbid any expression representable with numeric values other than $1$; i.e. not $x^2$ nor $3x$ nor $4$:

multilinear, no powers other than $1$: $x+xy \equiv x^1+x^1y^1$ is OK, but not $x^2+x^3y^4$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $x(x+y) \equiv x^2+y$;
all one, no coefficients other than $1$: $x+xy \equiv 1.x+1.xy$ is OK, but not $2x+3xy$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $a(x+y)+x(a+b) \equiv 2ax+ay+bx$ ; and
no constants other than $1$: again, in the fully expanded sum-of-products e.g. not $(a+1)+(b+1) \equiv a+b+2$

$Q.$ Is there an efficient algorithm to determine if two expressions are equivalent?

To illustrate, here's an inefficient brute-force algorithm with exponential time:

  expand both expressions fully to sum-of-products, which can easily be checked for equivalence (just ignore order, since commute/associate can reorder).

e.g.
$(a+b)(x+y) \rightarrow ax+ay+bx+by$
$a(x+y)+b(x+y) \rightarrow ax+ay+bx+by$

This seems a well-known problem - even high school students are taught manual ways to solve it. It's also solved by automated theorem provers/checkers, but they concentrate on more sophisticated aspects.

Here's a working online automated theorem prover: http://tryacl2.org/, which shows equivalence by finding a sequence of commute/associate/distribute etc:

$xy+x+y=x+y(x+1)$ ?
(thm (=  (+ (* x y) x y)  (+ x (* y (+ x 1)))  )) --- 188 steps

$y+x(y+1)=x+y(x+1)$ ?
(thm (=  (+ y (* x (+ y 1)))  (+ x (* y (+ x 1)))  )) --- 325 steps

This is my first question here, so please let me know if I've chosen the wrong place, wrong tags, wrong way of describing/asking etc. Thanks!
NB: this question has been rewritten in response to comments
Thanks to all responders! I've learned a lot.


texts: What are the steps/tricks/tips to construct a Büchi automaton from a given language?

texts:
Let's say I have this language: $(a + bc)^∗((b + c)a^ω + (abb^∗)^ω)$

It seems pretty complicated, where should I begin with if I were to construct a Büchi automaton?

I've been doing it the following way with smaller language sets:

a $^*$ operator is usually a path coming from a node to the same node.
a $+$ draws 2 branches

how would $^ω$ be represented? there are other operators, which I have not seen yet, what are they and how would they also be represented?

Pardon me if this is a silly question, but I'd rather ask than not knowing the answer ever.

Any help is greatly appreciated.
Thang


texts: What are some of these "high-level" instructions found in CISC architectures?

texts:
The Wikipedia article on complex instruction set computing says

  Before the RISC philosophy became prominent, many computer architects tried to bridge the so-called semantic gap, i.e. to design instruction sets that directly supported high-level programming constructs such as procedure calls, loop control, and complex addressing modes, allowing data structure and array accesses to be combined into single instructions.

What do these "high-level" instructions that can handle loops look like? What does an instruction for a procedure call (strikes me as something of a nebulous term to use here) look like? Can a loop instruction be strung together with multiple instructions for multiple conditions like in a C loop? Does "procedure call" mean something like an instruction that can pass parameters to a function? "High-level" means nothing here without examples.


texts: Express a number as a sum of consecutive primes (How many ways?)

texts:
I found this problem on codeforces in an ACM archive.

Given a number $n$, find the number possible of ways of expressing that number as a sum of consecutive primes. Example :

Given $n = 41$:

$41 = 41 =  2 +5+3 +7 + 11 + 13 = 11 + 13 + 17$

As we can see, there are three ways of writing $41$ as a sum of consecutive primes, keeping in mind that since $41$ is a prime, a sum that consists of only $41$ is a valid sum as well.

Knowing that $n \leq 10000$, list the number of ways you can express the input numbers as sums of consecutive primes.

My effort regarding this problem consists of the following :

Given that the max $n $ is $10000 $, I populated a vector of primes using the sieve of eratosthenes (its size is precisely $1229$).

Following, I computed a vector of prefix sums, such that at index $p$ of that particular vector, we have the sum of all consecutive primes up to inclusively $p$ (non prime indexed entries are equal to $0$).

For example: $\text{prime_sums[2] = 2 }, \text{ prime_sums[3] =5 },\text{ prime_sums[5] = 10}$, etc.

Now, using this particular vector we could simply do traversals of the  sum array for each of the input numbers and upon finding a way to write it as a sum (by comparing its value with that of each sum we encounter) , we would do multiple subtractions between elements of the sum array in order to find other possible ways to express our number as a sum of consecutive primes.

But this kills the speed of the program and feels really inelegant and awkward. Can you suggest alternative ways?


texts: What are possible uses for cross, back and forward edges after the DFS visit?

texts:
The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles.

What are other useful algorithms that use these labels?


texts: What does a polynomial time reduction mean?

texts:
I am having a little trouble understanding what is meant by a poly-time reduction.
Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean that the algorithm that solves $A$ using $B$ as a helper runs in $O(n^k)$ for some $k$?

So for example suppose:

$A$ is an algorithm that takes as input a list of numbers and returns whether there is a sublist whose sum is $0$.

$B$ is an algorithm that takes as input a list of numbers, and an integer $k$, and returns whether there is a sublist of length $k$ whose sum is $0$.

Then

def A(L):
     for i in range (1, len(L)+1)"
           if B(L, i):
                return true
     return false

Since this $A$ calling $B$ as a helper runs in $O(n)$ so can this be described as a polytime reduction from $A$ to $B$?