texts: Assigning edge weights under shortest path constraints

texts:
We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{a,b}: R\times R \rightarrow \mathbb{R^+}$ where $\mathbb{R}^+$ is all positive ($> 0$) reals ($c_{a,b} = c_{b,a}$ for all $a,b$ and $c_{a,a} = 0$ for all $a$ ). Our edge weight assignment is constrained by the requirement that for all vertex pairs $(a,b)\in R\times R$, all paths from $a$ to $b$ need to have at least weight $c_{a,b}$  where the weight of the path is the sum of all edge weights on that path.

Now assume that there exists an assignment such that for all vertex pairs $(a,b)\in R \times R $ there exists at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$.

Now consider the assignment of edge weights (*) that satisfies the constraints and minimizes the total sum of edge weights. Is it true that for all vertex pairs $(a,b)\in R \times R$ there will exist at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$ ?

My thoughts: consider, out of all assignments which satisfy the constraints and have for all vertex pairs $(a,b)\in R \times R $ there exists at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$, the one which minimizes the total sum of edge weights. Assume towards contradiction that for the assignment (*) that there exists a vertex pair in $ R \times R$ s.t. for all paths between these vertices all paths are strictly larger than the required constraint. and i'm hoping this yields a contradiction.


texts: Number of states in minimal Non Deterministic Finite Automata

texts:
What will be the number of states in minimal NFA that can be designed
  to accept the language $L = \left \{ \epsilon  \right \}$ having a non
  empty alphabet set?

My friends are saying that this can be done using $1$ state, make the only state start state & final state without any transitions.

But will not this NFA accept every string over the alphabet set?
Because for every input string we are already in accepting state.
So every string will be accepted.
My claim is that at least $2$ states will be required so that we can get away from that default accepting state (start state) on any non empty string and the minimal NFA will be exactly same as the minimal DFA accepting $L$.

Am I correct?


texts: How to build a graph of people where node connections are determined by name and age?

texts:
I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question):
Given a list of Persons, and two arbitrary Persons out of that list, we need to find the minimum nth-degree relationship between them.
Here are the definitions of Person and a "relationship":

A Person is defined as having 2 properties: Name and Age:
class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

A relationship between two Persons is defined as follows:

Two Persons are considered to be in a 1st-degree relationship if they have either the same name or the same age.
Two Persons are considered to be in a nth-degree relationship if they have n people of 1st-degree connecting them.

Example input:
Given the following list of Persons:
persons = [{ Name = "John", Age = 60 }, { Name = "John", Age = 50 }, { Name = "Ted", Age = 50 }]

Then:

The two Johns have a 1st degree relationship (because they have the same name).
The second John and Ted have a 1st degree relationship (because they have the same age).
Hence, the first John and Ted have a 2nd degree relationship (because the second John connects them).

Now, I understand that it's a simple Dijkstra's algorithm question, but what I don't know is how should we build the graph of Persons?
I'm looking for an algorithm, but preferably code, that can build the graph in a time complexity which is better than $O(|V|^2)$.
If you think this question can be solved without building a graph (e.g., using BFS as mentioned in the comments), please let me know how can this be done, but I still want to know how to build the graph.


texts: Minimal number of animals in a matching card game

texts:
I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The game is for the child to find the animal that is common to both cards. I began to wonder how many animals the company would need to draw in order to produce such a set of cards.

So here's the question, more formally. Given N cards with K animals on each card, what is the minimum number of unique animals required such that there exists at least one collection of animals on cards where each card shares precisely one animal with each other card.


texts: create large data sets for machine learning

texts:
I am trying to research a new topic using machine learning. The problem is, I have a very small dataset, consisting of 5 months of data. I have been told that my dataset is too small. I want to know if there is any way of making my dataset larger, using an automated tool/algorithm I can implement fast, and more than that, if it is a good idea.

My dataset contains also months with peculiar data (or outliers) and they have cases from generic and standard to unexpected data.

I mention that I have already searched for similar datasets on the available websites. The dataset I am interested in it's about personal budgets, incomes, expenses, consumer behavior.


texts: Communication senario: A sends to B or B sends to A

texts:
Consider processes A and B and the situation where either A will send a message to B or B will send a message to A. Is there a standard algorithm for this scenario that makes sure that exactly one of these two interaction took place?

In a naive implementation where both A and B decide independently whether to send or receive there is the case where both of them decide to send. In such a case the requirement of exactly one interaction is not met. Is there a correct implementation? Are there any references?


texts: How does the OS handle multiple stacks in its physical memory?

texts:
Without assuming ASLR...
Processes have virtual addresses, and they manage stacks & heaps of their own. However, these all get mapped to physical addresses somewhere on the memory.
Let's say we have Process A and Process B. Process A starts before Process B. Process A puts some stuff on the stack. We switch to Process B. It puts some stuff on the stack.
However, Process A finishes, and all its elements need to be removed off the stack. However, Process B's elements are still on the stack, so we can't just force the stack pointer down.
How is this relieved? Or is physical memory really all heap?


texts: Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?

texts:
My understanding of non-deterministic algorithms is that they're "as lucky as you want".

...you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices v and w, if there's a vw path, then you can non-deterministically walk a vw path, luckily correctly guessing the vertices to walk in a vw path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I'm not sure.
Therefore, my first question is: if you can non-deterministically walk a vw path, can you non-deterministically walk a Hamiltonian path from v to w, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I'm calling a "least Hamiltonian path." I would think so, but I'm not sure.
Define the least Hamiltonian path from v to w to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider K5 the graph with vertices {1,2,3,4,5} and all possible edges, then the least Hamiltonian path for (v,w) = (2,3) is 21453. If you were at vertex 2, the next least vertex would be 1. Then, the next least vertex would 4. etc.
Therefore, my actual question is: Given graph G and vertices v and w can you non-deterministically walk the least Hamiltonian path from v to w, if it exists?
Motivation: If so, then perhaps there's a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices v and w, and go through each pair of vertices such that v<w, checking for the existence of a least Hamiltonian path. To ensure all vertices in G are reached, keep a counter for the number of vertices walked (this should equal N if there are N vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from v to w will be unique, therefore it can be walked multiple times (each time you walk through it, starting at v, you'll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated - one for the vertex you're checking to see if it's unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).


texts: Rules of converting a weighted digraph to an undirected graph?

texts:
What are the rules of converting a weighted digraph to a weighted, undirected graph?

I understand that the edges should go in both directions from vertex to vertex. However, do the weights of each edge to/from other edges need to be the same? If not, how does one decide which weight to attach to the undirected vertices?

For example, can this adjacency matrix representation of a weighted digraph be converted into an undirected weighted graph?


texts:
So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ?

$\text{My Attempt at the Proof}$:-

Suppose there isn't , then there must be at-least one edge common in both the paths , and if we remove it then it disconnects $G$ and thus is a bridge. As there are no Bridges , Hence Proved !

$\text{Why I feel this Proof is incorrect }$:-

Suppose the exits three paths from u to v.

Path 1 :- $u$ ----> $E_1$ -----> $E_2$ -----> $v$

Path 2 :- $u$ ----> $E_2$ -----> $E_3$ -----> $v$

Path 3 :- $u$ ----> $E_1$ -----> $E_3$ -----> $v$

(here -----> represents some path and $E_1 , E_2 , E_3$ represent Edges.

This is an example which violates the above property. It has no bridges as well as no edge disjoint paths.

Can someone either Prove or disprove this Property ? I am really confused.


texts: Voronoi diagram with given number of vertices and sites

texts:
I want to draw a Voronoi diagram with 9 sites and with

no vertex,
1 vertex,
4 vertices, and
7 vertices.

How do I approach this question. The one with no vertex is easy, it can be done by collinear points. What about the others.

A figure for each would be appreciated.


texts:
I am working with an iterative application in a distributed setup. The application has n processes (P1, P2,...Pn) and m iterations. Each process may or may not perform any computation in a given iteration. Initially, each process (and its associated data) is assigned to a separate Virtual Machines (i.e. the first iteration starts with n VMs).

Each process requires different CPU time in each iteration. I am looking at this problem as an instance of bin packing problem. For a given iteration, I fix the bin capacity as the maximum CPU time required by a process in that iteration and migrate the processes to the minimum number of VMs. The migration of process has a cost associated with it.

My goal is to execute the application with minimum cost and minimum increase in makespan of the application.

(The minimum makespan can be achieved by assigning each process to a separate VM but that will increase the cost. Each VM has a single CPU core so when we assign multiple processes to same VM, they execute sequentially. Memory is not a constraint.)

In each iteration, I use bin-packing algorithm to find a minimum number of bins and use the Hungarian algorithm to map bins to VMs.

But sometimes, the cost of migration exceeds the maximum CPU time required in the given iteration, In which case migration becomes an overhead.

Is the problem described above, a variation of bin packing problem? Any suggestions on how to approach this optimization problem.


texts:
I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation?

Also, would an algorithm be considered the high level description or the implementation level description of the procedure you need to do?


texts: Efficiently calculate values based on subsets of a list

texts:
Let's say I have a list of items, each of which has some value
Eg. L1 = [A, B, C, ...]

And another list of items L2: [1, 2, 3, ...]. Each of the items in L2 needs to calculate the max value of a subset of the items in L1
Eg. Item 1 wants max(A,B,C) , item 2 wants max (D,E,F) , etc.

I cannot figure out how to calculate all these values efficiently.

I initially thought of using dynamic programming so that, after 1 calculates max(A,B,C), we store it in a hash table to save time when another item wants the max of the same subset (A,B,C), but I've just realized that it is theoretically possible to have a worst case where every item in L2 wants the max of a unique subset of elements in L1.

For example, using the combinations formula

Combinations(n,r) = n! / r! / (n-r)!

If L1 has 10 items (n), and each item in L2 wants the max of a unique subset of 5 items (r) of L1, that's already 252 possible combinations, giving me an exponential time algorithm!

So, is there some existing algorithm to efficiently calculate the values of all these unique subsets?
I'm sure there's some algorithm that deals with this (something to do with trees, I think?), but I just can't recall it.


texts: Can somebody suggest what is wrong with these constraint?

texts:
I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances.

For example, the washing machine is appliance indicated by i, which has set of the task like washing, rinsing and spinning etc., indicated by j. Here we divided the 24 hours into 96-time slots each time slot has 15 min indicated by k.

The constraint 1. Says that the tasks of the task of the appliance have to exclusive. It means they should not overlap with each other.

$X_{k,u,i,j} +  Y_{k,u,i,j} +  Z_{k,u,i,j}$ $\leq$ $X_{k,u,i,j-1} +  Y_{k,u,i,j-1} +  Z_{k,u,i,j-1}$ --------------- 1

$j \in \{2,. . .n_i\}$

The constraint 2 says that the task of the appliances has to sequential and operate continuously without any interruption.

$\sum_{k=t}^{t+H_i -1} \sum_{j=1}^{n_i} X_{k,u,i,j} +  Y_{k,u,i,j} +  Z_{k,u,i,j} \geq 1$ --------------- 2

$\forall  i \in N$,

$j \in \{1,. . .n_i\}$,

$k = \{1,2,. . .96\}$,

$u \in \{1,2,3. .. 50\}$,

$X_{k,u,i,j}, Y_{k,u,i,j}, Z_{k,u,i,j} \in \{0,1\}$

$X_{k,u,i,j}$  indicates whether task j of appliance i  at time slot k processed by electricity or not; 1 = task processed; 0 = not processed

$Y_{k,u,i,j}$ indicates whether task j of appliance i at time slot k processed by natural gas or not; 1 = task processed; 0 = not processed

$Z_{k,u,i,j}$ indicates whether task j of appliance i at time slot k processed by hot water or not; 1 = task processed; 0 = not processed

i index of the appliance.

j index of the task of the appliance.

k index of the time slot(1time slot = 15 min).

u index of each home.

$H_{i}$ is the operation time of the appliance i.

Do both constraints satisfies my condition?.

It would be great if somebody validates.


texts: Big-O notation for lower bound instead of Big-Omega

texts:
In the Wikipedia's Binary search tree, one can read

Traversal requires $O(n)$ time, since it must visit every node.

Since it is question of a lower bound, shouldn't we write

Traversal requires $\Omega$(n) time, since it must visit every node.

Is the $O(n)$ statement here even correct?


texts: Grammar that numbers of letters `c` is greater than number of letters `b`

texts:
Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.

Example: $acbccba$ is generated by the grammar.

I thought about:

$S \rightarrow aS \mid bS \mid SCS$

$ C \rightarrow cb \mid ca$

but not sure if it works. Could you help me, please.


texts: Optimization of coefficients by using genetic algorithm

texts:
I want to optimization the coefficient of FIR filter using genetic algorithm method.

The main data structures in the Genetic Algorithm are:

chromosomes (vector)

objective function values

fitness values

If the objective function is :

and

in the passband

in the stopband

How to determine the objective function ?


texts:
Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?

Thanks.


texts: Haskell: implementation issues of some basic features

texts: I'm taking a "Programming Language: Design and Implementation" course and our professor asked to make a case study about: Haskell programming language. In this case study he asks to make a report about: "implementation issues of some basic features. Can anybody list any good sources for this?


texts: Precise runtime of the algorithm to find number of digits in an integer

texts:
Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm

count = 1;
while ( (value = value/10) )    count++;

Now, what is the time cost of this algorithm? If we assume that k is the number of bits ( not digits) required to represent the number, then it is O(k). But this algorithm doesn't have a clean linear behavior. That is, if I double the the number of bits in the integer, the number of iterations of while loop doesn't necessarily double every time. An increase of 3-4 bits in the input increases the iteration count by 1.

I know that the number of digits in a number N is floor(log10(N)) + 1 but then we wouldn't be expressing the runtime in terms of number of bits, which is what I need.

In such cases how to calculate the runtime precisely?


texts: Proving that PP is closed under symmetric difference

texts:
I want to prove that PP is under symmertic difference.
let A be a language in PP and B likewise.
I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed under union , I should be done.
How do I show A\B in PP?
Am I on the right track? Maybe there is an easier way?


texts:
I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, appear to show the algorithm stopping after finding the first path as the white blocks spreading out on the linked video do not cover the whole area before the path is highlighted, implying that not all nodes are visited.

Does the algorithm, therefore, not visit every node and instead stop after the first path is found? If so, is it not possible that a more optimum path could exist than the one found?


texts: Difference between regular expression and grammar in automata

texts:
I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to differentiate between regular expressions and grammar of a language( I have not been taught the grammar for regular expressions).

I understand that grammar helps us to generate the valid strings in a language, but then this is what the rules for defining a regular expressions state. So where does the difference lie? I asked my professor and he said that regex are the most basic strings in a language and grammar is the set of rules for any language, which are of higher order than regex. Can someone provide some more in-depth information?


texts: Is $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

texts:
Is the language $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

Note: $x^R$ is the reverse of $x$.

My Work: I think this is a context free language. Since a pushdown automaton (PDA) accepts context-free languages, I am trying to draw a PDA for this language. When I draw a PDA, how does the PDA tell $x$ and $y$ apart?
Or is this not a context-free language? (then I can use pumping length to prove this)


texts: the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs

texts:
Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair.
My attempt
For example, if there are 4 players sitting around a  circular table there can be 9 distinct arrangements.

F1,F2,F3,F4
F2,F1,F3,F4
F2,F1,F4,F3
F4,F2,F3,F1
F1,F3,F2,F4
F1,F2,F4,F3
F4,F1,F2,F3
F2,F3,F4,F1
F4,F3,F2,F1

Now, I am stuck here. How can calculate this and what about larger values of N such as 50?
I tried using vectors and pushing back every element and do the reverse operators and swap elements but I am not sure whether this is correct or not.


texts: Bipartite Perfect Matching "Assignment Problem" - finding an assignment of a particular weight

texts:
The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to enumerate assignments one-by-one in increasing order of their weights using methods like Murty's algorithm, where each new enumeration takes polynomial time.

We can assume that there are 2n vertices in the bipartite graph and that the weights on all present edges are non negative integers less than some value k. Missing edges will need a higher weight or infinity.

My questions is, is it possible to find an assignment of a particular weight (that is not minimal), say W, in polynomial time? Naively, if one tries to enumerate assignments, it may take exponential time to find an assignment of weight W since there may be exponentially many assignments of weight less than W.

Further, if it is possible to find an assignment of weight W in polytime, is it possible to enumerate all assignments of weight W, similar to Murty's algorithm?

I know that we can formulate the assignment problem as a linear program

$\min \sum_{i,j} w_{i,j}x_{i,j} $

such that

$\sum_i x_{i,j} =1$
$\sum_j x_{i,j} =1$
$x_{ij} \ge 0$

I am not sure whether we can directly add the constraint
$\sum_{i,j} w_{i,j}x_{i,j} \ge W$
and still obtain integral solutions for $x_{i,j}$s. Thoughts?


texts: For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata)

texts:
Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0}
I’m trying to design a PDA. My aproach is:

-for every 2 ‘a’ push an ‘a’

-for every 4 ‘c’ push a ‘c’

-then pop them to solve the 2nd half of the language

This is the first part to count 2 ‘a’, but the ‘c’part is not very clear:

Any hints or solutions for the problem: ‘’for every 4 ‘c’ push a ‘c’ on the stack‘’

Thanks!


texts: Element-wise merging and re-sorting lists of sorted elements

texts:
Imagine you have a vector of pairs $(id, x)$ where $id \in I$, some set of opaque identifiers (hereafter, ids), and $x \in \mathbb{N}$ some value. Assume that every $id$ value is unique in your list. You can sort such a list on the $x$ values - below we will generally refer to this as a sorted list.
Given two such sorted lists $l_1, l_2$, I'm interested in merging and re-sorting the lists. Assume for now that the two lists both have length $s$, and the set of $id$ values appearing in $l_1$ is equal to the set appearing in $l_2$, and denote this set as $D$.
My merging I mean creating a merged list $l_m$, of the same length as $l_1$ and $l_2$, which has as its elements $(a, x_1 + x_2)$ where $x_1$ and $x_2$ are the corresponding values from the element $(a, x)$ with the same id $a$ in $l_1$ and $l_2$ respectively.
The the re-sorting simply involves sorting the merged list by its value in the same way as the input lists.
So really it's simple: take a two lists of integer values tagged by some id, add the values for corresponding ids to get a single list and sort it, quickly. That last part is the key - I don't want to throw away all the information already in the two sorted input lists and just sort the merged lists from scratch.
Since you already have the two sorted input lists, you can put some bounds on the position of many of the elements in the final list. For example, if a given id appears in position $j$ in the first list and position $k$ in the second list, then it must appear no later than position $j + k$ in the sorted list (of course, this bound is useful only for the elements where $j + k < s$). A similar bound applies for the position of each element measured from the end of the list - the element must appear in the last $2s - j - k$ elements of the list.
Are those bounds helpful in sorting the list? Better bounds can be calculated on the fly after examining some elements from the top of the list, but it's not clear to be how to use it.
I'm interested both in the case where the $id \leftrightarrow value$ relationship is uncorrelated, but also especially in the case where there is a correlation between them across the input lists (i.e., ids with large (small) values in $l_1$ are more likely to have large (small) values in $l_2$). That correlation holds in many real word data sets.
It seems like this type of operation would be common for any type of distributed query and sorting system. For example, imagine a system which records of the form $(string, value)$, much like the tuples above, except that each $string$ could appear many times, and you want to issue a query to return all unique strings, along with the sum of all their values for each string (this is just a select string,sum(values) group by string type query in a database). With distributed record storage, you'd expect a list of already-sorted tuples coming back just as described above, and your reduce step should merge and re-sort as described$^1$.

$^1$ Of course, you could argue that you simply don't sort the partial results from each distributed node, since it may be better simply to merge and then do a final sort once the results are reduced across all nodes - but this ignores the fact that reduce time is more valuable than distributed calculated time, since only the latter is effectively parallelizable. So you want to push as much work as possible to the distributed calculation, including the sort.


texts: Can someone give me the resolution procedure for 2 SAT, which is O (nˆ2)

texts:
According to Wikipedia, Even, S .; Itai, A .; Shamir, A. cited it in "On the complexity of time table and multi-commodity flow problems".

The paper can be found here: http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1975/CS/CS0059.pdf

EDIT: Reference [5] of the above paper can be found here:
https://www.jstor.org/stable/2310460


texts: What makes an operational semantics good?

texts:
Some papers define an operational semantics of a programming language. That is nice, but what makes such a semantics fit for the purpose?

An idea is to have a progress theorem, i.e. well-formed expression is either a value or a reduction can take place

another is type preservation, that an reduction preserves the type of an expression.

What else is a test for the adequateness of a semantics? What should I prove about it?


texts: Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?

texts:
1) (cited from "Introduction to the Theory of Computation" by Michael Sipser)

  Let $M$ be a Turing machine, we say that $M$ decides a language $L$ if $M$ is a decider which recognizes $L$.

2) (cited from "Computational complexity: a modern approach" by Boaz Barak and Sanjeev Arora)

  Let $f \colon \Sigma^{∗} \rightarrow \Sigma^{∗}$ and let $T \colon \mathbb{N}
 \rightarrow \mathbb{N}$ be some functions, and let $M$ be a Turing machine. We say that $M$ computes $f$ if for every $x \in \Sigma^{∗}$, whenever $M$ is initialized to the start configuration on input $x$, then it halts with $f (x)$ written on its output tape.

I think these two definitions shows two different functions of TMs, and it seems that there is not conflict between them.

So, given a computable total function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$ ?


texts: Solving a multivariate equation for asymptotic complexity

texts:
I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation

$$\begin{align}
T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c_0 \log n + c_1.\\
T(m,\ 1) &= T\bigl(\frac{m}{2}, 1 \bigr) + c_1 \\
T(0,\ n) &= 1 \\
T(m,\ 0) &= 1
\end{align}$$

I can see that for fixed $m$, this is $O(n)$, and for fixed $n$, this is $O(m)$. But I don't see how I can get an expression that characterizes the performance in terms of variable $m$ and $n$.

How can I solve this to find the asymptotic complexity in terms of $m$ and $n$?


texts: Construct a deterministic finite automation

texts:
The question asks to:

  construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\{0, 1\}^n$ for every n.

I have no idea where to start to constructing the DFA, could you give some directions?
By the way, how many states should this DFA have?


texts: Number of graphs that satisfies the property that edge weight is maximum of node values on which the edge is incident

texts: I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be assigned to the nodes such that the graph satisfies the condition that for every edge its edge weight is exactly equal to maximum of two node values this edge is incident on.


texts: Determining on whether topology is a tree or a hypercube

texts:
Assume that the nodes know that the topology G is either a hypercube or a
tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to reach terminal state TREE if G is a tree, terminal state HYPERCUBE if instead it is a hypercube. Let n be the number of nodes and m the number of edges, you would like to exchange O(m) messages in the worst case.

I will use DFS until I either:

reach a leaf or
a node that has been visited before.

In the first case it is a tree and in the second one it is a hypercube. How does this sound?

In the below code, I assume every the graph is tree. But If I see cycle, I change the STATE to HYPERCube. This happens when a node gets the token twice.

Sample Pseudocode

Initiator
    Spontaneously
    begin
        Unvisited:= N(x);
        initiator:= true;
        VISIT;
    end

IDLE
    Receving(T)
    begin
        entry = sender;
        unvisited:= N(x) - {sender};
        VISIT;
        STATE = "TREE";
    end

VISITED
    Receiving(T)
    begin
        STATE = "HYPERCUBE"
    end

    Receiving(R)
    begin
        VISIT;
    end

Procedure VISIT
begin
    if Unvisited =! 0 then
        next = Unvisited
        send(T) to next;
        become VISITED
    else
        if not (initiator) then send(Return) to entry endif
        become DONE;
    endif
end


texts: What is Harrison hashing, its applications in web search engines?

texts:
What is Harrison hashing and what are its applications in web searching?
Can some one give me some relevant information?

Update:

I found it here , and is a part of M.Tech syllabus of a friend of mine. I need to explain him this concept and then see how it can be applied in web applications.
Many thanks for spending your precious time.


texts:
Let's say I receive a large sequence $s$ of numbers $n_0$, $n_1$, $n_2$, $\ldots$ Later I expect to receive the same sequence $s^*$ with the same numbers  $n_0$, $n_1$, $n_2$, $\ldots$ but errors might occur. For instance $n_2$ gets altered. I'd like to detect errors as soon as possible with high probability.

solution: store cumulative hash sum every $k$ elements (but here I detect the error too late)
solution: store the whole sequence (way too large to store on disk)

Is there anything in between those two trade-offs that allows me to detect the error per element with high probability?


texts:
I am reading the paper Foundations and tools for the static analysis of Ethereum contracts, by Grischenko et al.
Sometimes the authors speak about hyper properties (e.g. Section 5).
What exactly is a hyper property in this context?


texts: For what special cases does this vertex cover algorithm fail or work?

texts:
I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are probably some graphs for which this algorithm will not work.

I need some help in finding the flaw in this algorithm and also, an indication for what restrictions should be imposed on graphs such that this algorithm works.

In the algorithm below I have a graph $G=(V,E)$. I also define the $\text{priority}(v)$ function; in rough terms, it is the number of edges that are covered by vertex $v$. The function has the property that

$$\sum_{v \in V} \text{priority}(v) = \text{number of edges}.$$

In other words, an edge is counted as covered by only one of its vertices, not both.

Define degree : V -> NaturalNumbers
degree(v) = number of edges connected to v, for all v in V

Define priority : V -> NaturalNumbers
Initialize priority(v) = 0 for all v in V

For all (u, v) in E:
    If degree(u) >= degree(v):
        priority(u) = priority(u) + 1
    Else
        priority(v) = priority(v) + 1

Define S as the solution to the vertex cover problem
Initialize S to the empty set

For all v in V:
    If priority(v) != 0:
        Add v to the set S

Output S as the solution


texts: Using half float to represent scaled short (int16), do I lose precision comparing to using double?

texts:
A device is generating 14-bit integer which is stored as int16 (short), a scaling process will then scale the data to value of order 10E-3.

Does it then matter if I store these number with half float or single float? Suppose the scaling factors are just single float.


texts: Is 0-1 integer linear programming with only equality constraints NP-Hard?

texts:
We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it

$$\min c^T x \text{ s.t. } Ax = b \quad x_i \in \{0,1\}\quad (i=1,2,...,n)$$


texts: Asymptotic growth of a function containing a sum

texts: How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails I take the limis of f'(x)/g'(x). But I'm not sure what to do in the following task (to prove whether the marked statement is true or not):


texts:
I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the boolean hypercube but am unable to generalize to an arbitrary regular graph:

"Suppose we run Valiant’s scheme on an N-node network in which every node is of degree d; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is
$
\Omega\left(\frac{\log N}{d \log \log N} + \frac{\log N}{\log d}\right)
$."

I understand that the diameter of any $d$-regular graph is always $O(N/d)$, but am not sure how the analysis would still work in this case as for the hypercube.

I have a feeling that the first term relates to the coupon collector's problem, but am completely unaware of how to get the second term.

Edit: Yuval in the comments essentially has a "workaround" proof that works, but isn't related to the scheme itself, and seems very unintended by the book authors. Is there another solution?


texts:
I'm having trouble determining the correct way (if there is one) to find the witnesses in any given big O problem.

The example I'm struggling with:
$2^x + 17$ is $O(3^x)$.

I am expected to find two witnesses such that $2^x + 17 \leq C(3^x)$ whenever $x > k$.

Unfortunately, my textbook isn't very clear on how to actually find them and rather suggests to more or less guess until you get both constants to work. It is to my understanding that if one pair exists, infinitely many do.

How do you find these?


texts:
I am new in complexity theory and have a doubt.
If you have a language (alphabet) L (for example {"a";"b";"Y","0","1","◄"}) and a Dictionary D (for example {"abY";"Ú■";"ba";"000001◄";"FFG","342"}) Output all the words in D that can be generated by the symbols in L So, for the example above a program will output: "abY";"ba";"000001◄" Question is: is this problem in NP?
Thank you in advance.


texts:
We have $h_1(n)$ and $h_2(n)$ which are both admissible heuristics. We know that $h_1(n) < h_2(n)$ for every state $n$ in a search problem.

Now we are given two heuristics $h_3(n)=\frac{h_1(n)}{1+h_2(n)}$ and $h_4(n)=\frac{h_2(n)}{1+h1(n)}$ and we want to prove $h_3(n)$ and $h_4(n)$ are both admissible.


texts: polynomial time reducibility, if $A \in \mathbf P$ and $B \in \mathbf N$ $\mathbf P \setminus \{\emptyset,\Sigma^*\} $ and vice versa

texts:
$f: \Sigma^* \to \Sigma^*$ is a polynomial time computable function if some poly-time Turing Machine M, on every input w, halts with just $f(w)$ on its tape.

Language $A$ is polynomial time reducible to language $B$, written $A \le_p B $, if there is some polytime computable function $f: \Sigma^* \to \Sigma^*$ such that:
$w \in A \iff f(w) \in B$.

I wonder if either $(i)$ or $(ii)$ is correct:

$(i)$ If $A \in \mathbf P$ and $B \in  \mathbf N$$\mathbf P \setminus \{\emptyset,\Sigma^*\} $, then $A$ is polynomial reducible to $B$.

$(ii)$ If $A \in \mathbf N$$\mathbf P  \setminus \{\emptyset,\Sigma^*\}$ and $B \in  \mathbf P  $, then $A$ is  not polynomial reducible to $B$.


texts: Stable marriage problem with only one side having preferences

texts:
I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and through a series of proposals, we end up with a stable matching.

Thinking of it like medical schools and applicants, each medical school has a different number of slots available, so is there an intuitive or simple augmentation to the basic algorithm that solves this case?

The second question is, what if only one side has a preference ranking? For example, say medical students have preferences, but the schools do not, and simply have some number of spaces available (different between each school). All (or many of) the students (say 50 students) prefer school A, but it only has 5 slots or so. Is it possible to determine if there is a "matching" that allows everyone to get a choice in their top 3 or top 5 or something along those lines?

Clearly, if schools A, B, C have only 5 slots each, and 10 students rank the schools 1. A, 2. B, 3. C it is not possible for everyone to have their top 3. There are 30 "wants" and only 15 available slots. What I am interested in is determining if it possible and if possible, finding one of those matchings.

If this question makes no sense I can try to elaborate the specific use case it came up in.


texts: Constructing hitting sets for randomized algorithms

texts:
Suppose A($\cdot$,$\cdot$) is an efficient randomized algorithm and L is a language such that

$\text{If }x \in L, \text{Pr}_r[(A(x,r) = 1)] = 1$ and if $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \frac{1}{2}$.

Let $H$ be a hitting set such that for all inputs $x$ of length $n$, if $x \notin L$, then $\exists y \in H, A(x, y) = 0$.

We need to show that there exists a hitting set $H$ of size $O(n)$.

My idea is that from the condition $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \frac{1}{2}$, we can get that $x \notin L, \text{Pr}_r[A(x, r) = 1] < \frac{1}{2}$. Then we can randomly choose $y_1$, $y_2$, ..., $y_m$ to construct a set $S$. Then for any input $x \notin L, \Pi_{i = 1}^{i = m}Pr[A(x, y_i) = 1] < 2^{-m}$. Therefore, the probability that there exists at least one $y_i$ such that $A(x, y_i) = 0$ is $1 - 2^{-m}$. Now the problem is if we need to prove the hitting set $H$ must exist, then $1 - 2^{-m}$ should be 1, which means $m$ should be large enough. However, I cannot find the relationship between $m$ and $n$ and how come if $m$ in size of $O(n)$ would prove such $y_i$ must exist.

Or maybe I am going in the wrong way. Can somebody help me with this?
Any help would be appreciated.
Thanks in advance.


texts: How to detect number of specific object in an image and it's diameter(size)?

texts:
I have two images of IRON RODS (i.e only two images) and I want to detect how many rods are there in each image and get the diameter of each rod in a image?

I don't know where to start as there are lot of articles regarding object detection and it's hard to find one for my use-case.

If you can help me with a abstract view on how to model such requirement? Please point me a right direction.

Doubt:

1) How can I train with two images and then how to count numbers of rods are there in each image and retrieve it's diameter?


texts: NP-Complete is not closed under kleene star

texts: Consider $\Sigma=\{0,1\}$. Suppose that $L \subset \Sigma^*$ is $NP-$Complete. How can I prove that $L' = L \cup \{0,1\}$ is $NP-$Complete?


texts:
Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by
$$  L' = \{ \alpha \in \Sigma^* \mid (\exists \beta \in \Sigma^*)[ |\alpha| = 2 |\beta| \wedge  \alpha\beta \in L \}.$$
As far as I understand, I have to construct an automaton $A'$ that recognizes the language $L$.

I was thinking of making the automaton so it has two pointers, one pointing at the beginning states and one at the final states, and the automaton states are the cartesian product of the automaton states from $A$, and the left pointer is going to move 2 states to the right, and the right pointer 1 state to the left. Any suggestions?


texts:
My question is in the context of a paging virtual memory system.

THE PREMISES:

The function of resident set management (RSM) is to:

Impose an upper bound on the cardinality of a process' resident set.

The ostensible benefits of RSM are:

Reduce the overall page fault rate by preventing one process from dominating memory.
Increase the probability that the process scheduler will find a "ready" process at any particular time by increasing number of processes that can reside in main memory.

The potential drawbacks of RSM are:

Increase a process' page fault rate if the upper bound on its resident set is smaller than its working set.
More overhead.

When a page fault occurs, the thread of execution that caused the page fault is blocked and another thread(s) is allowed to execute in the meantime.

THE QUESTION:

Isn't resident set management superfluous?

Here's why I think it's superfluous:

A single process would not be able to "dominate" memory at the expense of other processes anyway.  This is because whenever a single large process creates a memory fault and causes a non-resident of its own to be swapped in and some other process' page to be swapped out, then another process(es) would be able to execute while the large process is blocked due to the memory fault.  If the other processes' working sets grow too small due to the single large process, then they will cause memory faults of their own and be able to reclaim pages.  This should eventually result in an appropriate equilibrium state.

(Or more realistically, frames would be reclaimed according to some LRU algorithm or the like, and so wouldn't be needed anyway.  And if they were needed, then the system is probably in a state of thrashing, and the total number of processes should be constrained, rather than the number of resident pages per process.)

There should be enough processes in memory for the process scheduler to find a "ready" process at any particular time anyway.  This is because without RSM there are no specific limits to the number of processes that can be in main memory at one time.  New processes can be added simply by replacing current resident pages (e.g. LRU).  The number of resident pages per process would then result automatically from the interaction of the number of active processes, the size of the working set of every process, and the replacement algorithm.  No additional limit on the number of resident pages per process is necessary in a virtual memory system (vs. an overlay system).

Disclaimer:  I'm a student in an "intro to OS concepts" course right now.  My information comes from my textbook and my professor.  However, neither my textbook nor the professor was able to answer this question, and I wasn't able to find a pre-existing similar question on StackExchange in a cursory search.  I'd appreciate any corrections if my question is nonsensical or has already been answered!


texts: $\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$

texts:
Hello for a homework I have to show that deciding whether a regex over $\Sigma = \{0,1\}$ descibes $\Sigma^*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).

The thing which irrs me is that I think this problem is in $\mathsf{P}$.

Here is my argumentation:

Let $R$ be a regex, then we have $$L(R) = \{0,1\}^* \Leftrightarrow \overline{L(R)} = \varnothing$$

Given $R$ we can consruct an NFA with $\epsilon$ moves for $L(R)$ in poly. time; eliminating the $\epsilon$ moves (again poly. time: $O(|Q| \cdot |\delta| \cdot |\Sigma|)$) we obtain an NFA $M$.

By toggling the accepting states of $M$ we can construct an NFA which accepts $\overline {L(R)}$, whose emptiness we can check with a BFS (again in poly. time).

$\leadsto \mathsf{RegExpEq_{*}} \in \mathsf{P}$

Where does my argumentation shatter? If both my argumentation and the question is correct, then $\mathsf{P} = \mathsf{coNP}$ which seems highly doubtful.


texts: Why does counting sort copy the input elements?

texts:
When I was reading about counting sort in Introduction to Algorithms for the first time, I stopped reading after the step where they calculate the number of each element in the input array. It's the first thing we do after allocating an auxiliary array.

I was sure the algorithm would look like this:

public static int[] countingSort2(int[] input, int k) {
    // 0 <= input[i] < k
    int[] result = new int[input.length];
    int[] auxiliary = new int[k];

    for (int j = 0; j < input.length; j++) {
        auxiliary[input[j]] = auxiliary[input[j]] + 1;
    }

    int resultIndex = 0;
    for (int i = 0; i < auxiliary.length; i++) {
        if (auxiliary[i] != 0) {
            for (int m = 0; m < auxiliary[i]; m++) {
                result[resultIndex++] = i;
            }
        }
    }
    return result;
}

But of course, the canonical implementation is different:

public static int[] countingSort(int[] a, int k) {
    int c[] = new int[k];
    for (int i = 0; i < a.length; i++)
        c[a[i]]++;

    for (int i = 1; i < k; i++)
        c[i] += c[i - 1];

    int b[] = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--)
        b[--c[a[i]]] = a[i];

    return b;
}

I wonder why they needed to fill the auxiliary array again and then put elements of the input array to the output array.


texts: How to Generate Control flow graph from a Petri net model?

texts: My research is mainly focused on generating test sequences automatically using Colored Petri net.CFG provides techniques for generating test sequences. But some papers says that, test sequence generation methods based on a control flow graph sometimes suffers from a feasibility problem (i.e. some paths in a CFG may not be feasible).So I need a technique to draw a Control flow graph from the Colored Petri net model, in a way that, when I will select paths from the control-flow graph it will contain only the feasible paths.Then I will generate test sequences from the CFG. Can anyone help me finding any technique please or give me any suggession??


texts: What does the "Lambda" in "Lambda calculus" stand for?

texts:
I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from.

Can anyone explain the origins of the term?


texts: How do we know that the reduction is correct?

texts:
I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable.

Here's my reasoning:

Let's say that we want to find out if the following problem is decidable: given any machine $M$ and a string $y$ find out whether the machine $M$ ever writes an $@$ symbol on the tape.

So, I intuitively think that this is an undecidable problem and I try to reduce the halting problem to our problem.

Let's have an arbitrary machine $N$ and a string $x$. If $N\#x \in HP$ then $N$ halts on input $x$ else if $N\#x \not\in HP$ then $N$ loops on input $x$ where $HP = \{ M\#x\ |\ M\ \text{halts on}\ x\}$.

Here's my first question: how do we know if $N\#x$ belongs to $HP$ or not? I thought that we cannot tell and that's the whole idea behind the halting problem.
Now we typically construct a machine $M'$ which has $N\#x$ hardcoded inside and which output doesn't depend on its input. Here's how $M'$ works:

Erase the input.
Run $N$ on $x$.
If $N$ halts on $x$ then have $M'$ write $@$ to the tape. Otherwise, if $N$ loops on $x$ then have $M'$ make sure $@$ is not written on the tape.

From what I understand, the proof is over as the behaviour of $M'$ is similar to $HP$ (I am not sure if this is the correct way to formulate this) and since the halting problem is undecidable then our problem is undecidable as well.

Here comes my second question: why does it prove anything? It looks like any problem could be treated this way leading us to the conclusion that everything is undecidable as we were able to incorporate the halting problem in our algorithm. How do I know that there is no way to avoid an undecidable problem in my algorithm? I feel like we're showing that we can use the halting problem to solve my problem instead of showing that solving my problem would result in solving the halting problem as well.

I'm sorry if my explanation is a little bit vague – I've already consulted my professor, read related chapters in Automata and Computability by Kozen and tried to read tutorials and presentations on the Internet but I still cannot understand the logic behind the reduction. I'd be grateful if someone could explain my misunderstanding.


texts: What happens when there are two same IP addresses?

texts: IPv4 addresses run out few years ago. But everywhere I can see mine or someone elses IP address it's in IPv4, not IPv6. I understand that world switched to IPv6? So why we can see address in older format? Does that mean somewhere someone can have same address as I? How can that work?


texts: How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)?

texts:
I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords.
As far as I know, to calculate the number of errors to be corrected and/or detected someone must know the Hamming distance between 2 codewords. However, I do not have any relevant information to find out a solution to this question. I tried to calculate the efficiency of this code using the formula:
(E = Number of original message bits / length of the codeword). The efficiency in my case is 1/5. But, I do not know how can I use this information to calculate the number of errors that can be corrected and detected.


texts: Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals

texts:
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:

Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ to $n$ do begin
$\quad$ for $j:=1$ to $i-1$ do begin
$\quad\quad$ for each production of the form $A_i \to A_j\alpha$ do begin
$\quad\quad\quad$ remove $A_i \to A_j\alpha$ from the grammar
$\quad\quad\quad$ for each production of the form $A_j \to \beta$ do begin
$\quad\quad\quad\quad$ add $A_i \to \beta\alpha$ to the grammar
$\quad\quad\quad$ end
$\quad\quad$ end
$\quad$ end
$\quad$ transform the $A_i$-productions to eliminate direct left recursion
end

According to this document, the efficiency of the algorithm crucially depends on the ordering of the nonterminals chosen in the beginning; the paper discusses this issue in detail and suggest optimisations.
Some notation:

We will say that a symbol $X$ is a direct left corner of
a nonterminal $A$, if there is an $A$-production with $X$ as the left-most symbol on the right-hand side. We define the left-corner relation to be the reflexive transitive closure of the direct-left-corner relation, and we define the proper-left-corner relation to be the transitive closure of
the direct-left-corner relation. A nonterminal is left recursive if it is a proper left corner of itself; a nonterminal is directly left recursive if it is a direct left corner of itself; and a nonterminal is indirectly left recursive if it is left recursive, but not directly left recursive.

Here is what the authors propose:

In the inner loop of Paull’s algorithm, for nonterminals $A_i$ and $A_j$, such that $i > j$ and $A_j$ is a direct left corner of $A_i$, we replace all occurrences of $A_j$ as a direct left corner of $A_i$ with all possible expansions of $A_j$.
This only contributes to elimination of left recursion from the grammar if $A_i$ is a left-recursive nonterminal, and $A_j$ lies on a path that makes $A_i$ left recursive; that is, if $A_i$ is a left corner of $A_j$ (in addition to $A_j$ being a left corner of $A_i$).
We could eliminate replacements that are useless in removing left recursion if we could order the nonterminals of the grammar so that, if $i > j$ and $A_j$ is a direct left corner of $A_i$, then $A_i$ is also a left corner of $A_j$.
We can achieve this by ordering the nonterminals in decreasing order of the number of distinct left corners they have.
Since the left-corner relation is transitive, if C is a direct left corner of B, every left corner of C is also a left corner of B.
In addition, since we defined the left-corner relation to be reflexive, B is a left corner of itself.
Hence, if C is a direct left corner of B, it must follow B in decreasing order of number of distinct left corners, unless B is a left corner of C.

All I want is to know how to order the nonterminals in the beginning, but I don't get it from the paper. Can someone explain it in a simpler way? Pseudocode would help me to understand it better.


texts: Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good

texts:
Suppose that I want to enumerate all English language words of length 5.
If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations.
However, suppose that I can check a partial specification to see if there are any words consistent with it.
By partial specification I mean an assignment of some letters to some positions, with the others free to vary. E.g. "is there a word that starts with "HO" and ends with "Y" (but has any of the 2^26 configurations of third and fourth letter)?
An obvious algorithm would be to formulate it as a 26-tree, and traverse it depth-first, stopping once a pattern was deemed not "good" (e.g. as far as I'm aware there are no five letter words in English that start with "AAA", so we can skip checking "AAAAA", "AAAAB", ..., "AAAZZ").
Is it possible to do any better (average, worst case)? How about under additional assumptions on the distribution of letters (any such learning would need to be part of the algorithm, since my actual problem is not about natural language)? As another view on the second question: what sorts of heuristics are helpful?


texts: In my theoretical CS class, we learned about Interior Point Methods for convex optimization, but it seems that projected subgradient descent works equally well for constrained optimization. What are the benefits of using Interior Point Methods?


texts:
My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices.

It sounds like it should be simple to create such a tree, but I can't imagine one, my bisections are always better balanced. Can somebody show me a tree where the vertex distribution of 3/4 to 1/4?

This is from "Introduction to Algorithms" by Thomas Cormen, 3rd edition, MIT Press. Appendix B, Problems B-3.


texts: Lower bound on the number of comparisons needed for finding the two largest elements

texts:
Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log_2(n) - 2 comparisons. Prove that any algorithm will have to perform at least n +log_2(n) - 2 comparisons in order to find both elements.

What I've done: I tried to compare it to a tennis tournament(sort of a binary tree that compare pairs of competitors in which each game has a winner and a loser - each winner goes up to the next level in the tree). It takes n-1 comparisons and every element is involved in a comparison log n times at most.

The biggest element will be the winner in the tournament. the second biggest element will have to face the winner so he's one of the log n elements the the winner competed against which means logn -1 comparisons. If I sum it all I get what I need to prove.

I got this note from the teacher: the proof is not correct because you assume the algorithm uses a tournament you have to prove any algorithm has an input for which the second largest element is in a group of size logn.

Can someone tell me how the proof should have looked like? I'm really struggling with it. Please be detailed as possible


texts:
Can we distinguish instruction level parallelism and SIMD instructions (SSE, 3D now...) ?

Or is SIMD instructions one of the multiple ILP techniques ?

Thank you.


texts: A lambda calculus evaluation involving Church numerals

texts:
I understand that a Church numeral $c_n$ looks like $\lambda s. \lambda z. s$ (... n times ...) $s\;z$. This means nothing more than "the function $s$ applied $n$ times to the function $z$".

A possible definition of the $\mathtt{times}$ function is the following: $\mathtt{times} = \lambda m. \lambda n. \lambda s. m \; (n\; s)$. Looking at the body, I understand the logic behind the function. However, when I start evaluating, I get stuck. I will illustrate it with an example:

$$\begin{align*}
 (\lambda m. \lambda n. \lambda s. m \; (n\; s))(\lambda s.\lambda z.s\;s\;z)(\lambda s.\lambda z.s\;s\;s\;z) \mspace{-4em} \\
 \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; ((\lambda s.\lambda z.s\;s\;s\;z)\; s)) \\
 \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; (\lambda z.s\;s\;s\;z) \\
 \to^*& \lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z
\end{align*}$$

Now in this situation, if I first apply $(\lambda z.s\;s\;s\;z)\;z$, I get to the desired result. However, if I apply $(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)$ first, as I should because application is associative from the left, I get a wrong result:

$\lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \to \lambda s. \lambda z.(s\;s\;s\;(\lambda z.s\;s\;s\;z))\;\;z$

I can no longer reduce this. What am I doing wrong? The result should be $\lambda s. \lambda z.s\;s\;s\;s\;s\;s\;z$


texts:
Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in coins in the least number of coins possible. So we have k type of coins and a limited amount of each type. Also the machine has an unlimited amount of each of the k types of coins so it can return us the exact amount it should (there is always coin with value 1). So we want to minimize the number of coins we have after we have paid for the items we have bought. Consider this example: We have 3 kinds of coins of values 1, 2 and 4 and we have to pay 15 dollars. We have 10 coins with value 1, 7 coins with value 4 and 5 coins with value 2. There are multiple ways to minimize our coins after the process. One of them is to give the machine 10 coins with value 1 and 3 coins with value 2. Thus we have paid 16 dollars with 13 coins and the machine should return to us 1 dollar and it returns us 1 coin with value 1. So we have spent 12 coins. The other way is to give the machine 9 coins with value 1 and 3 coins with value 2 and the machine doesn't return us anything. So we have paid 12 coins.

My approach to the problem is to divide the problem to two separate coin change problem. The easier problem is when the machine returns us the extra amount of money we have paid. I think this is a simple coin change problem that we want to change some amount of money to the minimum number of coins. The main problem is to pay the machine some maximal amount of coin with the restrictions mentioned above. The restrictions were that we have limited number of each coin and if want to pay A dollars the machine stops receiving coins when the amount of money we have paid becomes equal or greater than A. So For example if we have to pay to 15 dollars and we want to use a total amount of 18 dollars to pay we should use at least a coin with value 4 (18-15+1) or else at some point in the process of paying the amount we have given to the machine surpasses 15 and it won't receive any more coins.

So what I have done so far is this

A //amount we should pay
D //value of the coin with max value among all present coin types
for value_to_change in A to A+D-1
   clear the memoized table for maximal_change
   r = maximal_change(value_to_change,0,0)
   d = minimal_change(value_to_change-A)
   ans = max( ans, r-d )

max_coin // the maximum value of the coin we have used so far
maximal_change( value_to_change, index_of_coin_type, max_coin )
   if we have computed (value_to_change, index_of_coin_type)
       return the computed value
   if (it is the last coin type) AND (max_coin > A-value_to_change)
       if value_to_change % value[index_of_coin_type]==0
            return value_to_change / value[index_of_coin_type]
       else
            return we cant change this value with this coin // -1
   for i in [0, number_of_available_coins_with_this_type]
       n = maximal_change( value_to_change - i*value_of_this_coin_type,
                           index_of_coin_type+1,
                           max(max_coin, value_of_this_coin_type) )
       if n != -1 // we can change the value
           result = max(n+i, result)
   dp[value_to_change][index_of_coin_type] = result;
   return result

now my problem is my solution is slower than what is expected and I think it is because that I clear the memoized table for every value to change. This is only because in each value to change we are required to use a coin with value at least (value_to_change-A+1). Anybody has a better solution?

link of the full description of the problem
link of my implementation


texts:
My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf
had this interesting problem:

  1-28. [5] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

What's the lower bound for asymptotic complexity of this problem?   `

P.S: I know repeated subtraction with a will work. It has asymptotic linear complexity with b (case where a = 1). However, repeated subtraction has exponential complexity with $n$ where $n$ is the number of bits needed to represent the number. Specifically it is $\Theta(2^n)$. So it is definitely not fast.


texts: Determining whether a digital circuit is optimal

texts:
Are there any techniques that can be used to determine whether a digital logic circuit is optimal, or if it has extraneous operations that don't contribute to the output?

I'm especially curious in the case where the circuit is defined in terms of XOR and AND gates.

I know I could make a karnaugh map and create a circuit from that, but that doesn't really tell me about the circuit I had, it just gives me another circuit.

Thanks for any info!


texts: How to build a set of closed chains with a sequence of different vertices?

texts:
I have a set of many bi-directional links like
A-B, A-C, B-C, A-D, C-D, D-E, etc.

I need to find a set of many closed chains with a sequence of different vertices (vertex-disjoint cycles).
It would be better if I can find them all.

How I solve the problem right now:

I build a directed graph by these links.
I take one of the vertices and then go to the others by edges, building walks.
I take the last walks' vertices one by one and then go to the others vertices except those that have already passed, continue building walks.
Repeat step 3 for each walk until I reach the start vertex.
4a. If other vertices are over and I could not build a closed chain, I delete the walk.

I apologize for my ignorance of graph theory.
Perhaps I am reinventing the wheel?
Perhaps there is already a solution to this issue?
Please tell me.

Additional information:

The set of links is about 10,000.
The directed graph may have unconnected islands of subgraphs.

What problems in my realization I want to solve:

I have to build many walks that will be deleted sooner or later because they are not closed chains.
I have to check which vertices have already been passed in order to get the next ones.

UPDATE

For what I want to apply it.

I need to filter out incoming incorrect currency pairs' data by their prices. Every currency pair has two current prices: (best) ask and (best) bid. The currency pair's data will be considered valid if it is possible to build an unprofitable exchanging closed chain (vertex-disjoint cycle) containing at least 4 vertices. (Cycle A-B-A is always valid.)

The closed chain is considered unprofitable when the product of the chain's asks is bigger than 1 and the product of the chain's bids is less than 1.

$\prod A_i>1,$

$\prod B_i<1$

In this case, each currency pair in the chain is valid.

At the same time, finding an invalid chain is not a consequence of the fact that the data is invalid. Only the failure to find a valid chain will be it.


texts:
We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) Turing machine that for $n$ given, halts after exactly $f(n)$ steps, and just asked if we could now prove that $n!$ is fully time constructible (and moved on).

I am not sure how the proof goes, but I am thinking it has to use $n^k$ time constructability to some extent, or some identity involving factorials, since we showed $n^k$ is (fully) time constructible using $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Hints would be appreciated too, really. Thanks in advance.


texts: Computing Cardinality of Sumsets using Convolutions and FFT

texts: I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?


texts: Can minimum or maximum height of the binary search tree be constrained by the position of some elements

texts:
I came across one problem, which read as follows:

  We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there are fewer than 15 elements, we have some flexibility as to the structure of the tree. Which letters can appear at the root? For each possible root, which letters can be the left child of the root? The right child? Find the true statement in the list below.

  G cannot be the root.
  It is not possible for B to the left child of the root and K the right child of the root of the same tree.
  It is not possible for B to the left child of the root and J the right child of the root of the same tree.
  It is not possible for D to the left child of the root and K the right child of the root of the same tree.

I selected the option 2, and it was correct. However after some thinking I felt option B is also incorrect. And in fact now I am more confused with the meaning of the question itself.

First I am unable to fix what of the question is asking:

Given option is correct if with given option, we can build a valid BST of height 4 (considering root is at height 0)
Given option is correct if with given option, we cannot build a valid BST of height less than 4.

Should we call option 1 correct as we can build height 4 BST with root G as follows:

         G
       /  \
      /    \
     /      \
    D        I
   / \      / \
  B   F    H   L
 / \ /        / \
 A C E       K   M
            /
           J

or call incorrect since we can build height 3 (<4) BST with root G as follows:

         G
       /  \
      /    \
     /      \
    D        J
   / \      / \
  B   F    I   L
 / \ /    /   / \
 A C E    H   K M

Similarly I initially thought that there are 8 characters between B and K. One of them can be root. So 7 characters are remaining, with which we can build only 4-height BST. We cannot build BST with height less than 4. So somehow thinking this much I selected option 2. However, option says "It is not possible...". But it is vey much possible to build height 4 tree with B as left child and K as a right child of the root:

         G
       /  \
      /    \
     /      \
    B        K
   / \      / \
  A   D    I   M
     / \  / \ /
    C   F H J L
       /
      E

Similarly I can build height-4 tree with B as left child and J as right child of the root (as said not possible in option 3):

         G
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    I   L
     / \  /   / \
    C   F H   K M
       /
      E

Finally, I can build height-4 tree with D as left child and K as right child of the root (as said not possible in option 4):

           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    C   F    I   M
   /   /    / \ /
  B   E     H J L
 /
A

So what is correct interpretation of this question?

Somehow, if we try to generalize, I feel this question boils down to following:

  Whether the minimum and maximum height of the binary search tree is constrained, if we fix certain elements of the binary search tree to particular position (as in this case the immediate children of the root)?


texts: Notation for words with a common substring/factor

texts:
Let $A$ be an alphabet and $u,v\in A^{*}$ be words. If it exists $z, u', u'', v', v'' \in A^{*}$ such as: $u = u'zu'' $ and $v = v'zv''$ then $z$ is a substring (also known as factor) of both $u$ and $v$ (i.e. “common”).
Is there a fairly standard or acceptable notation to denote either:

The predicate: “$u$ and $v$ have a common substring/factor”
The set of substrings/factors commons to $u$ and $v$


texts: Is multiprocessing possible on a turing machine?

texts: I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?


texts:
The task is to compare two trees and determine what are the changes. Both trees are represented as an adjacency list (ID, ParentID).

Base tree:

A (ID: 1, ParentID: 1)

B1 (ID: 2, ParentID: 1)

C1 (ID: 6, ParentID: 2)

D1 (ID: 13, ParentID: 6)

C2 (ID: 7, ParentID: 2)

D2 (ID: 14, ParentID: 7)

B2 (ID: 3, ParentID: 1)

C3 (ID: 8, ParentID: 3)

D3 (ID: 15, ParentID: 8)

E1 (ID: 23, ParentID: 15)

B3 (ID: 4, ParentID: 1)

C4 (ID: 9, ParentID: 4)

D4 (ID: 16, ParentID: 9)

E2 (ID: 24, ParentID: 16)
E3 (ID: 25, ParentID: 16)

D5 (ID: 17, ParentID: 9)

E4 (ID: 26, ParentID: 17)
E5 (ID: 27, ParentID: 17)

C5 (ID: 10, ParentID: 4)

D6 (ID: 18, ParentID: 10)

B4 (ID: 5, ParentID: 1)

C6 (ID: 11, ParentID: 5)

D7 (ID: 19, ParentID: 11)
D8 (ID: 20, ParentID: 11)

C7 (ID: 12, ParentID: 5)

D9 (ID: 21, ParentID: 12)
D10 (ID: 22, ParentID: 12)

New tree:

A (ID: 1, ParentID: 1)

B1 (ID: 2, ParentID: 1)

C1 (ID: 6, ParentID: 2)

D1 (ID: 13, ParentID: 6)
D2 (ID: 14, ParentID: 6)

B1-C2 (ID: 7, ParentID: 2)

B2 (ID: 3, ParentID: 1)

C3 (ID: 8, ParentID: 3)

D3 (ID: 15, ParentID: 8)

E1 (ID: 23, ParentID: 15)

B3 (ID: 4, ParentID: 1)
B4 (ID: 5, ParentID: 1)

C4 (ID: 9, ParentID: 5)

D4 (ID: 16, ParentID: 9)

E2 (ID: 24, ParentID: 16)
E3 (ID: 25, ParentID: 16)

D5 (ID: 17, ParentID: 9)

E4 (ID: 26, ParentID: 17)
E5 (ID: 27, ParentID: 17)

C6 (ID: 11, ParentID: 5)

D8 (ID: 20, ParentID: 11)
D10 (ID: 22, ParentID: 11)

C7 (ID: 12, ParentID: 5)

C7-D7 (ID: 19, ParentID: 12)

Changes:

D2 (ID: 14) moved under C1 (ID: 6)
C4 (ID: 9) moved under B4 (ID: 5)
C2 (ID: 7) renamed to B1-C2
D7 (ID: 19) renamed to C7-D7 and moved under C7 (ID: 12)
D10 (ID: 22) moved under C6 (ID: 11)
C5 (ID: 10) removed
D9 (ID: 21) removed

One of the solutions can be to iterate through each node in the base tree, compare it to equivalent node in the new tree and then determine what is the change.

For example:

D2 (ID: 14, ParentID: 7)

the name is the same
ParentID changed to 6
that means D2 was moved

Is there a more efficient way to perform such comparison?
Is there a well known algorithm to solve this type of problem?


texts: Is huffman-encoding with distinct frequencies of symbols unique?

texts:
Say I have following text: "abbcccddddeeeee".
As you can see, each letter has a different frequency of occurence.
When making a Huffman-Trie to encode this String, will this trie be unique?

I thought a bit on the problem and I can't come to a definite conclusion, but I think the trie will NOT be unique. Say the begin-situation:

a(1) b(2) c(3) d(4) e(5)

To make a trie, we take the lowest frequencies together and make a node above it with the sum of those frequencies. Because the frequencies are all ascending, there is only 1 way to take the lowest nodes. In this case, a and b. If we keep going on further, it wel never occur that we need to choose 2 subtries out of a larger collection, there will always be just 2. When seeing this, you could conclude the trie will be unique BUT. I see never stated in which order the two subtries need to be added. For example, to make the first new subtrie, we can put node a left OR right of node B. We can do this at each level and eventually, this will flip some bits in the end-result.

Am I correct?


texts: Give a $3$-state DFA for $(01 \cup 1)^∗$

texts: How do I change the design to accept the given language, because I think my DFA can accept $001$ as well. Is that correct?


texts: How can a CPU access more memory locations than 2^wordsize?

texts: I noticed that CPU's like the 8086 and especially the 8080 have the ability to access more memory than what one would normally assume. The 8080, for example, has an 8-bit word size but can use a 16-bit memory address. From what I understand, a standard instruction has the opcode in the beginning and then the address on which it will work. How then, could a 8-bit processor be able to fit an opcode and 16-bit address in 8-bits?


texts: How does a computer distinguish two separate transmissions on a wire

texts:
My basic idea of networking at the lowest layer is that one computer will send a bunch of parallel bits at a time down a cable and another computer will read these bits.  For example, computer #1 sends a bunch of parallel bits to computer #2.  Computer #2 then gets the bits then waits for the next bunch of bits.  And so on.

I have a couple of questions about how this works and how we get around a few problems.

Problem #1: Say Computer #2 doesn't wait long enough for the next series of bits.  Computer #2 may accidentally read the first set of bits twice, messing up communication.

Problem #2: Computer #2 waits too long.  It doesn't read the second set of bits in time and only starts reading after the second set of bits are shown.

[to summarize problems 1 & 2, it seems like it would be very difficult to exactly sync the rate of transmition between the two computers)

Problem #3: We can't rely on every transmission to be different.  So it's not like we can just wait for the transmission to change and then store the new value.

Problem #4: Say we use a special phrase.  So after every transmission computer #1 signals to computer #2 that the transmission is going to change by flashing a bunch of 1's.  This is a problem because what if our data is a bunch of 1s?  We won't know if the transmission changed or not.

The only solution I can think of is to have some extra bit that alternates for each transmission, bit this seems like it wouldn't work for one-bit-at-a-time transmission networks like wifi. What part of all of this am I missing?  How is this problem solved in the real world?


texts: What are the meanings of metalanguage and metasyntax and EBNF?

texts:
I am trying to understand what BNF, metalanguage, and metasyntax are.

From https://proofwiki.org/wiki/Definition:Metalanguage

  A metalanguage of a formal language is a formal language used to
  specify the formal language (make statements about the formal
  language).

  The object language of a metalanguage is the language described by
  that metalanguage.

From https://proofwiki.org/wiki/Definition:Syntax

  The syntax of a formal language is its structure, and is specified by
  a formal grammar of the formal language.

So I wonder if a formal grammar of a formal language is a
metalanguage of the formal language?
From https://proofwiki.org/wiki/Definition:Metalanguage/Metasyntax

  The syntax of a metalanguage is called a metasyntax of the object
  language of that metalanguage.

From http://en.wikipedia.org/wiki/Extended_Backus–Naur_Form

  Extended Backus–Naur Form (EBNF) is a family of metasyntax notations,
  any of which can be used to express a context-free grammar.

Does it mean that a context-free grammar is a metalanguage of a
context-free language, and EBNF is a syntax for the context-free grammar as a metalanguage, and therefore EBNF is a metasyntax for the context-free language as a object language?
From http://en.wikipedia.org/wiki/Metasyntax

  A metasyntax describes the allowable structure and composition of
  phrases and sentences of a metalanguage, which is used to describe
  either a natural language or a computer programming language.

  Some of the widely used formal metalanguages for computer languages
  are Backus–Naur Form (BNF), Extended Backus–Naur Form (EBNF), Wirth
  syntax notation (WSN), and Augmented Backus–Naur Form (ABNF).

Does it mean that EBNF is a metalanguage of a formal language, and
this formal language is a context-free grammar?

Thanks and regards!


texts: How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

texts:
So here's the problem:

-You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid square is empty)

-You must minimize the number of empty grid squares by filling this grid with Tetris shapes which are each composed of exactly 4 blocks (a block is 1x1)

What is an algorithm that can consistently do this given any mxn partially-filled grid?


texts: How is substitution in type theory the composition of classifying morphisms in category theory?

texts:
In the article at nlab about relation between category theory and type theory, it is said that substitution in type theory is the same as composition of classifying morphisms in category theory.

Can you please explain why that is so for a newbie? And ellaborating on what exactly a classifying morphism is?!


texts: In any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree?

texts:
Recently, I am reading the book [1]. I am trying to solve the following problem:

1.2 Pigeons and holes. Properly speaking, we should call our representation of Königsberg a multigraph, since some pairs of vertices are connected to each other by more than one edge. A simple graph is one in which there are no multiple edges, and no self-loops.
Show that in any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree. Hint: if $n$ pigeons try to nest in $n - 1$ holes, at least one hole will contain more than one pigeon. This simple but important observation is called the pigeonhole principle.

The following is my attempt to solve the problem: Let $G$ be a finite simple graph that has $N_V$ vertices and $N_E$ edges. Because each edge connects two vertices, the number of total degrees is $2 N_E$. Let $d_i$ be the degree of the $i$th vertex for $i = 1, 2, ..., N_V$, then
$$\sum_{i = 1}^{N_V} d_i = 2 N_E. \tag{1}$$
On the other hand, we know
$$0 \leq d_i \leq N_V - 1. \tag{2}$$
When $d_i = 0$, it means that the $i$th vertex does not connect with any other vertices. A vertex can connect with at most $N_V - 1$ vertices.
Then I don't know how to continue. Could any one please tell me the correct solution? Thanks in advance.
Note: It is not my homework. I am just interested in solving the problem.
Reference:
[1] C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2015.


texts: I had this idea of program tohelp me in my everyday life. We both work and don't live in the same city. I was wondering how to make a program that calculate, depending on the work scheduleand the number of travel required between both our house, the best way to spend our weekend, like at which house we have to be and when to spend the maximum time together. I know this sound like a problem you'd get in a school book but i really cant think of how to do it.


texts: Can we make a non-regular language regular via concatentation?

texts: My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?


texts: Can I couple non-terminals in context-free grammars?

texts:
If I had productions like so...

$S \rightarrow A1B$

$A \rightarrow \epsilon$

$A \rightarrow 0$

$B \rightarrow \epsilon$

$B \rightarrow 1$

If I only want strings $\{\epsilon1\epsilon, 011\}$, am I allowed to choose when both $A$ and $B$ become $\epsilon$? Or will I get resulting strings such as $\epsilon11$ and $01\epsilon$? (I know the $\epsilon$'s disappear, but I just left them in to avoid confusion.)

If I get the unwanted strings, then how would you force both $A$ and $B$ to be $\epsilon$ only when you need them to be, while still having $A$ and $B$ result in different terminals?


texts: Modify Damerau–Levenshtein distance to allow reversals of longer substrings

texts:
Is there a way to modify the Damerau–Levenshtein distance algorithm to allow the transposition of substrings? By this I mean that instead of simply turning "ba" to "ab" you could calculate "worra" to "arrow" and have that cost only be 1. An example might help:

If you had a target of timeflieslikeanarrow and a staring string of tfemiliilzejeworrbna, you would have the following operations for a minimum of 6. (step 1 being the start and step 7 being the end, 6 actual operations).

tfemiliilzejeworrbna (the target)
tfemiliilzejeanbrrow (transpose)
tfemiliezlijeanbrrow (transpose)
timefliezlijeanbrrow (transpose)
timefliezlijeanarrow (a substitution)
timefliezlikeanarrow (a substitution)
timeflieslikeanarrow (a substitution)


texts: How to find the best parameters of a Genetic Algorithm applied to the TSP problem?

texts:
I have an assignement where I need to use a Genetic Algorithm to solve the TSP (Traveling Salesman Problem). I alrerady implemented a solution in C# but the problem is we're asked to use some kind of method to do the Parameters Tunning (For example to pick the population size, mutation rate, etc..). For now, I only try random values and test..

I tried looking for an example with Taguchi method but I don't seem to understand how would one implement it for a GA problem.

Can anyone put me in the right direction?


texts: How to know maximum final states in a DFA?

texts:
If a NFA contains N states, then Equivalent DFA can have atmost $2^N$ states.

Is there any method or any concept to know, how many final and non-final states will be there in the equivalent DFA ?

Take for example : An NFA has 7 states out of which 3 are final states. Its equivalent DFA can have atmost 128 states.

Then is there any method to find maximum number of final states and non final states in converted equivalent DFA ?


texts: Proving a language is not regular with pumping lemma

texts:
I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help me out, it'd be much appreciated.

\begin{equation}
A = \{a^n b^m c^l    \mid      n\leq m  \vee  m\leq l\}
\end{equation}


texts: Which AC-3 algorithm is being used here?

texts:
This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma, Humaira Tasnim Proma, Syed Mehrab Kabir and Rakib Ibna Hamid.

I am confused whether this is pure AC-3 or AC-3 with backtracking. Which one is it?


texts: What is the intuition behind the relationship between space and time for an algorithm?

texts: I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?


texts:
Let S be a system whose state can be altered by performing actions. Each action has two possible outcomes, and each outcome brings to a specific system state. A state is never visited two times, i.e., the state graph is a DAG (a tree, more specifically, where the root corresponds to the initial system state and each edge corresponds to an action). The probability of obtaining either one of the outcomes is known.

Notice that just B actions can be performed, and the pool of actions contains N different actions.

My objective is to devise an online optimal algorithm which identifies the best path to be taken, i.e., the path which guarantees the minimum cost. With the term "online" I am referencing to the following behavior:

An action is chosen
The system state is consequently modified
A new action is chosen (taking into account the system state modification performed ad 2.)
The system state is again modified according to the selected action
...

My first idea was the one of using A* in the following way:

I ask A* to find the best sequence S of B actions to be performed
I perform just the first action contained in S, and I modify the system state consequently (according to the outcome of the action)
I ask A* to find the best sequence S' of (B-1) actions to be performed
I perform just the first action contained in S' and I modify the system state consequently

The problem is that I don't know whether this solution is optimal (I didn't succeed in finding an optimality proof), and an optimal solution would be required in my case.

May you suggest another online algorithm (or, alternatively, a way of proving the optimality of the method I propose) to find an optimal solution for the problem?

EDIT: maybe something from game theory can be used instead (extensive form games with imperfect information). I am the player I that chooses the actions, while the player II is a dummy player that chooses the action "first-outcome" or "second-outcome", where "first-outcome" and "second-outcome" are my actions' possible outcomes.

NOTE: I posted a similar question here, although in my previous question an offline version was required, i.e., the modifications of the actions were not taken into account at each iteration.

Thanks in advance.


texts: A concrete example about string w and string x used in the proof of Rice's Theorem

texts:
So, in lectures about Rice's Theorem, reduction is usually used to proved the theorem. Reduction usually consists a construction of $M'$, using a TM $M$ which is in the form $\langle M,w \rangle$  to be simulated first, an input $x$ to be simulated if $M$ accepts. $M'$ accepts if x is accepted.

I really want a concrete input about $\langle M,w \rangle$  and $x$. For example:

  $L = \{ \langle M\rangle  \mid L(M) = \{\text{ stackoverflow }\}\}$, that is L contains all Turing machines whose languages contain one string: "stackoverflow". $L$ is undecidable.

What kind of $\langle M,w \rangle$ to be simulated?

Suppose we have input x = "stackoverflow" or x = "this is stackoverflow" or any x with "stackoverflow" in it.

What if we first simulate a TM $M$ selected from in the possibilities of all TMs, and this TM accepts only a single character $a$ as its language. So, we simulate this $\langle M,w \rangle$  with $w = a$, and surely it will be accepted. And then input $x$ is also accepted according to the definition of $L$.

So, we conclude that $\langle M,w \rangle$  in which language is a single $a$ is reducible to $L$ that accepts all TMs which have "stackoverflow"?

Edit: I've just looked up a brief definition of reduction. A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Given that definition, I think the correct TM $M$ with its description $\langle M,w \rangle$  in my example should be a TM such that it accepts regular languages. This is the harder problem. If this is solvable, then my trivial $L$ with one string is solvable. But apparently, it's not according to the proof. We can effectively say we reduced from language one string problem to regular language problem and try to solve it. Previously, I thought the other way around: $\langle M,w \rangle$  is reduced to one string problem.

Is my thinking correct?


texts: Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

texts: I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with two stacks. I also know that you can’t simulate a Turing machine with a PDA, because a professor challenged a student when he suggested the treating a stack as a matrix, that is, as if it were two arrays. What’s the roadblock?


texts: If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

texts:
Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

Is it true that a convex optimization can be NP-Hard? On one hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.
If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?


texts: How can I calculate the exponential integral?

texts:
(I'm not sure this is the right forum.)

I'm writing a program that uses the prime-counting function.  Right now, I'm using x/log(x), but I want to switch to something more accurate.  A better approximation is the logarithmic integral function (actually, its Eulerian variant), which can be computed from the exponential integral.  Now how can I compute the exponential integral?  I'm on a macOS Intel system using Swift, so I can use the various advanced floating-point functions provided by Apple's system libraries if needed to help.


texts: Can a finite automaton have more than one regular expression?

texts:
A finite automaton is a generator for a regular language, and a regular expression represents a regular language. A language can be represented in many forms of regular expressions.
So can a finite automaton have more than one regular expression?


texts:
I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular.

I should probably mention that by "decidable" I mean "being decidable by single-tape deterministic turing machine".

Thanks and regards
Guillermo


texts: Building vertex-edge visibility graph among polygonal obstacles on 2d plane

texts:
I want to implement algorithm for computing vertex-edge visibility graph among polygonal obstacles, but I can't find any description or scientific paper describing such algorithm. Currently I understand how to extend Lee's algorithm for vertex-vertex visibility graph to compute vertex-edge graph, but I want to achieve better than $O(n^2 log(n))$ complexity. I read paper of Mount and Ghosh about their $O(nlog(n))$ algorithm based on triangulation of free space, and seems it allows extension to produce vertex-edge graph. But that algo has too complicated implementation :)

I wonder if there is a way to extend Overmars and Welzl algorithm $O(n^2)$ or algorithm with similar complexity to produce vertex-edge visibility graph? It's implementation seems to be quite simple. Point me on some papers, links, or describe it here if you can.


texts: How can I minimize a time value given by a graph depending on a cost value given by another graph?

texts:
Consider a company that wants to lunch a new subsidiary. To do so, four phases are needed: A, B, C, D which have to be done in this order. The length of each depends on how much money is invested in the phase.

Assume that numbers the close to the red edges are for all red ones, and likewise for the purple ones.

Here is the graph labelled with time.

Here is the graph labelled with cost in M€.

Considering that we want to realize A and B spending at most €5M, what minimal length of time do we have to foresee? What path with cost1<5 minimizes cost2 (the time value)?

How can I handle this problem? Do I have to apply Bellman's algorithm without considering A prioritaire to B prioritaire, which costs €6M? I do not know what critical graphs are.

Do I first have to do a Bellman aglorithm for A and B on time knowing that I must not make my company pay more than 5M? And then A second algorithm from B prioritaire or B rapide, find all values I found and choose the fastest?

But I think that using two algorithms lead me to have several solutions.

I'm not asking for the whole solution, some hints would be really appreciated! ;)


texts: Fastest nth root algorithm to a lot of digits?

texts: What is that fastest algorithm that can calculate a lot of digits of a decimal root? For example: 10,000 digits of the 3.56th root of 60.1?


texts: Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

texts:
A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as in this question.

I've noticed that when solving such tasks, any algorithm for calculating the number of such combinatorial objects via a recurrence relation can be transformed into an algorithm to generate such combinatorial objects. My question is, is there a name for this technique? Is there a theorem which says when this is true?

For example, suppose I want to generate a random sequence of $n$ $1$s and $0$s, where there are no two adjacent $1$s. I can begin by letting $a[n]$ be the number of such sequences, and observe that
$$
a[n] = a[n-1] + a[n-2].
$$

(This is the Fibonacci relation.)
This allows me to efficiently calculate a table of $a[i]$ for $i = 1$ to $i = n$.
Now if I want to generate a random such sequence, all I have to do is:

Step 1: Generate a random value $r$ from $1$ to $a[n]$.

Step 2: Use the recurrence relation to locate a sub-term which corresponds to the $r$th sequence:

If $r \le a[n-1]$, recursively find the $r$th sequence counted by $a[n-1]$, and append a $0$.
Otherwise, if $a[n-1] < r \le a[n-1] + a[n-2]$, set $r' = r - a[n-1]$, and recursively find the $r'$th sequence counted by $a[n-2]$, and append a $01$.

What seems to be going on here is that, given any recurrence relation for $a[n]$, I can transform this into a recursive algorithm which returns the $r$th object counted by $a[n]$. I'm assuming this is well-known, so I would be interested in any references or classic results about this. In particular, this isn't just specific to the example $a[n]$, but should be true for any recurrence relation satisfying certain properties.

Also, I think this may be related to some research on random testing.