texts: Why ternary computers like Setun didn't catch on?

texts:
Why ternary computers like Setun didn't become popular despite being cheaper and more reliable than binary computers, and also having important computational advantages? We could have had cheaper computers for everyone.
Edit: The answers to question about binary system do not resolve my question, since Setun, as I understand it, was based on some sort of binary circuit which used 2-bit combinations to represent the three values, the fourth combination wasn't used. Thus an argument about non-binary circuits being non-reliable doesn't apply to Setun.


texts:
I have two postal codes (fixed size of 6 digits) to compare and return the mismatch score.
where the mismatch weight of initial indexes is higher, then keep reducing.

Example postal code 123456, with index[0] ==> 1 is northern region, and if index[0] ==> 2 is southern region. so it should have very high mismatch score 123456 and 223456. index[1] represents sub-region like state, index[3] is like county/district, and so on..
But maybe 111156 and 111160 are nearer sub locality should be having less mismatch score.

The output of my result should match the score in the percentile.

To achieve this, if I take weights like this Sum[0.45, 0.15, 0.1, 0.1, 0.1, 0.1] == 100% but fixed weights cannot differentiate index base, e.g. for input source postal 111111 than searching with 111152 is greater mismatch than searching with 111125 as if we sum the mismatch scores. Mismatch weights percentile [0.45, 0.15, 0.1, 0.1, 0.1, 0.1] states, if there is a mismatch, happens at index 2, 3, 4, 5 all has a penalty of 10%, but this results in 111152 and 111125 will have same mismatch score for actual postal code 11111. So we cannot differentiate between 111152 and 111125. But you see 111125 is closer to 111111.
This makes me think of cumulative percentile index percentile like [1, 0.55, 0.4, 0.3, 0.2, 0.1] but this also doesn't work. As the sum of mismatch score going more than 1.

Also, it is not worthy to rely on the difference of postal code, like `111000 - 110999`, though it has a difference of 1, this difference same for `111000 - 111001`.
Hence `(((double)diff/Math.pow(10, diff.length()))` is also not working to compute.
So taking diff between two postal code as 123 then
123/1000 * (penalty[diff.length()]) wont work, as we cannot directly rely on difference.

Examples:
If i prefer mismatch penalty like { 0.8d, 0.7d, 0.6d, 0.3d, 0.15d, .05d }
0.05% penalty if the last char is not matched.
0.80% penalty if the first char is not matched.
Apply some minor penalty for every mismatch; after the first mismatch.

{"input" , "toBeCompared", "matchScore"}
{"999999", "989999", 0.29}, //71% mismatched, 29% matched
{"999999", "998999", 0.39},
{"999999", "999899", 0.7 },
{"999999", "999989", 0.85},
{"999999", "999998", 0.95}, //95% matched

Also should be able to differentiate scores between varying numbers.
{"111225", "111223", 0.949},
{"111225", "111229", 0.948},

How to achieve this? Kindly help.


texts: Complexity of removing edges to eliminate a perfect matching

texts:
Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this problem?

I'm aware that perfect matching has a formulation as a max-flow. One approach is, therefore, to find a min-cut in a corresponding graph, and see how many edges need to be removed so that the max-flow cannot carry as much flow. The problem with this approach is that a different min-cut might require the deletion of fewer edges, so it seems like this involves looking at all the min cuts in a graph.


texts: According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?


texts: Finding a super-increasing sequence from a given public key

texts:
Given a public key $A$ for the 26 bit Merkle–Hellman knapsack cipher.
For brevity I only mention that the highest number in $A$ is 1220060160.
I have to find a trapdoor pair $(u,v^{-1})$ for $A$ such that $S = Av^{-1} \bmod u$ is superincreasing/
Also given is an approximate value of $(v^{-1})/u$: 0.3463790532.
My Thoughts:
The 26 numbers in $A$ are given. And we only have an approximate values of the ratio.
Since $A = vS \bmod u$ and the largest value in $A$ is 1220060160, $u$ must be at least 1220060160.
So I could write a program and loop over $u$ going from 1220060161 to infinity to get $v^{-1}$ for each value of $u$,
calculate $S$ and check whether it is super-increasing.
Is this a correct approach? Is there a better approach?


texts: What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

texts: I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor switches that will be required per multiply, in terms of $N$?


texts: How to go from a recurrence relation to a final complexity

texts:
I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation.

//Input: Adjacency matrix A[1..n, 1..n]) of an undirected graph G
//Output: 1 (true) if G is complete and 0 (false) otherwise
GraphComplete(A[1..n, 1..n]) {
  if ( n = 1 )
    return 1 //one-vertex graph is complete by definition
  else
    if not GraphComplete(A[0..n − 1, 0..n − 1])
      return 0
    else
      for ( j ← 1 to n − 1 ) do
        if ( A[n, j] = 0 )
          return 0
      end
      return 1
}

Here is what I believe is a valid and correct recurrence relation:

$\qquad \begin{align}
  T(1) &= 0 \\
  T(n) &= T(n-1) + n - 1 \quad \text{for } n \geq 2
\end{align}$

The "$n - 1$" is how many times the body of the for loop, specifically the "if A[n,j]=0" check, is executed.

The problem is, where do I go from here? How do I convert the above into something that actually shows what the resulting complexity is?


texts: How to check if two sequences of setoid members are mutual rotations?

texts:
Real world background: There are 2 independent sources of polygon definitions, with arbitrary parameters. Meaning each source has it's own floating point precision, starting point and orientation of vertices.

The problem is to find an algorithm, that would receive those 2 polygon definitions and by a certain margin declare them equal or not. If a cutting machine would receive those 2 inputs, would it cut out the same shapes? (Which is btw. the real motivation behind the problem.)

E.g.: If

  polygonA = ( (1.0001, 1.0002), (2.0000, 1.0001), (1.5001, 1.9998) )

  polygonB = ( (1.9998, 0.9999), (0.9999, 1.0002), (1.5002, 2.0001) )

and there is precision margin of 0.001 (i.e. 1 mm) then polygonA would be equal to polygonB.

This problem can formally formulated as follows:

Task and terminology

Assume we have a set $X$ and two sequences $S_1 = (a_1, a_2, \ldots,a_n)$ and $S_2 = (b_1, b_2, \ldots,b_n)$, where $a_i \in X, b_i \in X, \forall i \in [1..n]$.

We define, that two sequences are congruent and denote them $S_1 \cong S_2$ if $\exists k,l \in [1..n]$ such that $a_{k+i \pmod{n}}=b_{l+i \pmod{n}}, \forall i \in [1..n]$. (Plainly said, they would define the same cycle.) If $S_1 \cong S_2$ then we say that $S_1$ is a rotation of $S_2$ and vice-versa.

The task is to find an algorithm that determines if $S_1 \cong S_2$.

Problem

In the case that $X$ is a total order set the task can be solved quite easily with a linear algorithm. (Finding a lexicographical extremum of all rotations for both sequences and then comparing those extrema.)

The question is, is there linear algorithm if $X$ is a setoid? I.e. members of $X$ can be checked only for equivalence. If not, does at least exist an algorithm with a better complexity than brute force?


texts:
Unique SAT is defined as:

Given any SAT problem, does the SAT problem have exactly 1 solution?

As I understand it is co-NPHard. I am unclear how it is in co-NP

Assuming the problem has more than 1 solution, any 2 solutions can be a certificate of it being nonUnique. That part is coNP. Now, given a problem can be unsatisfiable, how do we get a certificate of no solution?
Its also said that an NP Oracle can solve this problem in polynomial time, but an NP Oracle just tells if the problem is satisfiable. So how is that possible?

Apologies but I have no clue regarding this version of SAT.


texts: How to prove that knapsack has no competitive algorithm

texts:
In online knapsack problem, items arrive one by one. Each time an item $i$ arrives, its weight $w_i$ is revealed. We would like to maximize, in an online fashion, the number of items placed in a bin of capacity $W$.
The proposition that I am trying to prove is that no deterministic competitive algorithm exists for this problem.
I did something like this: assume that an online algorithm decided to place an item $j$. Then the adversary can choose a sequence of items in a way that the online algorithm places only a single item. In other words, it chooses the sequence where $w_j=W$ and all other items have $w_i$ small enough to make the competitive ratio grows without bound.
This proof seems wrong because I did not fix the sequence of input beforehand, right? (My input sequence changes when the online algorithm changes.) I should fix the input, then prove that no online algorithm is competitive. How to do this?


texts: How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

texts:
There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met:

For each $i \geq 0$, $x(y^i)z \in A$
$|y| > 0$
$|xy| \leq p$

But if $i = 0$ then $|y|$ cannot be strictly greater than $0$. Isn't condition 1 contradicting condition 2? Isn't $y^0 = \varepsilon$?


texts: Three languages and how to decide if they are regular

texts:
From following languages which one is regular and why others are not?And what is the regular expression for regular one.

$L_1=  \{wxwy | x,y,w \in (a+b)^+\}$

$L_2 = \{xwyw | x,y,w \in (a+b)^+\}$

$L_3 = \{wxyw | x,y,w \in (a+b)^+\}$

Also where can I find these type of problems?


texts: Context-free grammar for all words not of the form w#w

texts: I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \{0,1\}^*\}$, but  I'm finding that the '#' really messes things up. Is the language even context-free?


texts: How exactly is this equation for insertion sort time complexity solved so that it shows it is linear?

texts:
Background

I am currently taking an Algorithm and Analysis course and doing some extra studying on my own from the text book. This is not a homework question or exercise even. I am just trying to understand completely how the authors are doing the combining of terms in the time/cost equation for Insertion-Sort.

I understand what is being shown up until we get to the actual equation. I understand that each line, barring the comment which is considered to not have a cost, has a constant cost c.

This is how they have broken down the time/cost for the algorithm in psuedo-code:

for j = 2 to A.length
    key = A[j]
//Insert A[j] into the sorted
     sequence A[1..j - 1]
i  = j - 1
while i > 0 and A[i] > key
    A[i + 1] = A[i]
    i = i - 1
A[i + 1] = key

Here's the cost/time for each line according to textbook:

$c_1n$
$c_2(n-1)$
0
0
$c_4(n - 1)$
$c_5 =\sum\nolimits_{j}^{n} 2t$
$c_6=\sum\nolimits_{j}^{n} 2{t - 1}$
$c_7=\sum\nolimits_{j}^{n} =2{t - 1}$
$c_8(n - 1)$

The best case run time of the algorithm is then given by:

  $$
T(n) = \ c_1(n) + c_2(n - 1) + c_4(n - 1) + c_5(n - 1) + c_8(n - 1)
$$

This is where I get confused. Somehow they combine all of these terms to simplify the equation but it's done in one step so I can not follow/reproduce it on my own. This is what they come up with:

  $$
  = (c_1 + c_2 + c_4 + c_5 + c_8)n - (c_2 + c_4 + c_5 + c_8)
$$

According to the author it can be expressed as $an + b$ and thus a linear function of $n$. As mentioned above, I don't know how they simplified the equation nor how it can be expressed as $an + b$. I do understand that it is in linear equation form. How do I make the leap or bridge the gap per say?


texts: Is there such thing as "sequential types"?

texts: I am wondering how you could possibly define the implementation of an imperative function as a type. Is it possible? Currently I only see the input parameters and output result used in the definition of a function type, but how could you also include the implementation in the type definition?


texts:
On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are represented on the figure). Is it possible to 'partition' the domain spanned by the union of these polygons into 'disjoint' polygons (with contacts only at the boundary)? To be more precise, I'd like to associate to all edges the surfaces for which the edge is contained in its boundary.

Please advise if I'm not clear enough and thanks in advance for any suggestions!


texts: Given only TLB Lookup time, and memory access time, can the TLB hit rate be negative?

texts:
I'm given the following problem:

  TLB lookup time is given as 8ns and memory access time for a computer
  system is given as 40ns. What should be the TLB miss rate to achieve
  effective memory access time 60ns ?

I use the following formula where x is the TLB Hit Rate, and (1-x) is the TLB miss rate:

TLB Hit Rate * TLB Lookup Time + TLB Miss Rate * (TLB Lookup Time + Memoery Access Time) = effective memory access time

8x + (1 – x)(8 + 40) = 60

And solving for x I get:

8x + (1 – x)(8 + 40) = 60
8x + (1 – x)(48) = 60
8x + 48 – 48x = 60
-40x = 12
X = -0.3

TLB Hit Rate = -30%
TLB Miss Rate = (1 – TLB Hit rate)
TLB Miss rate = (1 – (-.3))
TLB Miss Rate = 1.3
TLB Miss Rate = 130%

Is it possible in this case for the hit rate to be negative, and miss rate to be over 100%?  Or am I messing up on either the formula or the calculations?


texts:
This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to find an assignment matrix $A$ which is again an $n \times m$ binary matrix (contains ones and zeros) and if $A_{ij}$ is $1$ it shows $i$-th person from first group has assigned to $j$-th person of second group, and maximize $\displaystyle\sum_{i}\sum_{j} C_{ij}A_{ij}$, subject to following constraints:
$$
1)\;\; \forall i: \;\; \displaystyle\sum_{j} A_{ij} = 1 \\
2)\;\; \forall j: \;\; \displaystyle\sum_{i} A_{ij} \le 2
$$
how should I solve this problem?
*how should we solve if we have another matrix $D$ and we also want $\displaystyle\sum_{i} D_{ij}A_{ij} \le constant$ ?


texts: Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

texts:
I want to formally write the equivalence classes of the following language:
$$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$

I understand the definition of equivalence classes, yet struggle to come up with a clear intuitive answer.

The language is regular, therefore i'd expect finite equivalence classes.

It seems like the essence of the information I am looking for is only "what is the $k$-th bit from the right", which means i want to focus my attention on suffixes in the form of $\sigma y \in \{0,1\}^*$ where $|y|=k-1$, $\sigma\in \Sigma$.

I would highly appreciate some guidance that would build my intuition for finding equivalence classes in general, and in this specific case.


texts: Quantum computers and computable functions

texts:
A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate?

If a function is not computable? Does this mean it will never be computable? Even if we change the axioms which our mathematical system is based on or we find a contradiction in it? Are we never be able to find something in the universe which can calculate these functions?

Is that right?


texts: Benefit of Petri Net Transition as Separate Object

texts:
In learning about Timed Automata, Coloured Petri Nets, and Process Calculi, I am wondering what the benefit is of having the Petri Net transition be a separate type of node in Petri Nets.

It seems that you can model the same stuff (eventually) using Timed Automata or Process Calculi, which both only have states and transitions (as edges, not objects). Instead of transition nodes, you could just have two types of "state", one be the Petri net place, the other be the Petri net transition. Then this second node does all it's queuing/guarding/checking of the tokens and whatnot. So I'm not sure the benefit is of having transition be a separate object in Petri Nets, when it could just be a second kind of "place" or "state".

That makes me wonder if there is a generalization of Petri nets to arbitrary number of node types (where instead of just place/transition, you have x, y, z, ...). In this sense it seems that process calculi are a generalization of Petri Nets.


texts:
Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable.
Is the following variant also known to be undecidable?

PCP with commutative alphabet.
Given and alphabet $\Sigma = \{a_1, a_2, \ldots, a_K\}$ and $2N$ sequences $\gamma_1, \gamma_2, \ldots, \gamma_N, \delta_1, \delta_2, \ldots, \delta_N \in \Sigma^*$.
Determine if there is a sequence of integers $\{i_j\}_{j=1}^M$ such that for each $1 \leq j \leq M$, $i_j \in \{1, 2, \ldots, N\}$ and for each $1 \leq m \leq K$,

$\#(a_m, \gamma_{i_1} \gamma_{i_2} \ldots \gamma{i_M}) = \#(a_m, \delta_{i_1} \delta_{i_2} \ldots \delta_{i_M})$
where $\#(a, w)$ denotes the number of occurences of the symbol $a$ in the string $w$.

Notice why I used the term "commutative" for the alphabet: the order of the symbols in the strings does not matter; only the counts need to be equal.

In general, is any variant of (unbounded) PCP with commutative alphabet known to be decidable or undecidable?


texts: How to convert DFA to regex with State Elimination

texts:
I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states.

I have this difficult DFA i need help converting to RE:

using STATE ELIMINATION

if you could explain ripping state q1 from the DFA it would help a lot


texts: Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula?


texts:
I'm confused about the idea of constructing a decider for a language and i need some help with it.

For example, if i have an enumerator M1 for a language L and another enumerator M2 for the complement of L, how do i construct a decider for L that uses both enumerator M1 and M2?

I understand that i would first introduce a Turing Machine with an input string and simulate it but I'm lost in the next stage of constructing a decider. By the way, enumerators are Turing Machines that outputs a sequence of strings.

Could anyone please explain on how do i construct a decider for the language L that uses both enumerators M1 and M2?


texts: What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?


texts:
2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1
since 2^n may or not be element of O(3^n)
I need a hint to figure the problem


texts: What is the best known data structure for online dk-NNG?

texts:
I want to build the distance constrained k-Nearest Neighbours Graph, i.e. for every point $p$ in the data cloud $P$ there are at most $k$ undirected edges to points that are closest among all possible vertices using $L_2$ metric with additional constraint that are no further than $d$.

There are only insertions (in batches of $10^6$ points) and neighbourhood retrieval queries used. The results have to be exact - I cannot use approximate nearest neighbours or reduce dimensions.

The setting is following:
There are 50 dimensions, not correlated. The $k=9$ is number of neighbours, $d$ is given distance. The data is sparse in every dimension, mean and median are meaningful, data is random and unstructured in any way (but for sure not from uniform or Gaussian distribution).

So far I have tried to build parallel kd-tree with partial rebalancing, the ball trees, m-trees, r-trees, Sparse ktree (octree with more dimensions) partitioning and two-projection hashes. But I am facing problem, that either insertion time is far too long or k-nng queries are too long. I think this happens because the structures are either static or not really prepared to maintain full neighbourhood graph.

I have tried linear scan, it performs good for very small data, worse than z-curve localised version or sparse ktree. Up to some $n$ it outperforms any treelike structure. I made one modification to naïve algorithm: used one AVL (right threaded) per dimension keeping nodes connected among trees and checked only points within distance $d$ at each dimension - this one performs well, but due to its memory consumption and lack of multidimensional structure scales poorly.

What data structure would be the best in practice for dk-NNG?
If this is not enough, I would like to optimize the number of neighbours checked, for localised data the number of bins traversed.


texts: Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

texts:
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as minimal average cost cycles, but use Bellman-Ford to discover a minimal cycle and augment along the discovered cycle. Let $V$ be the number of nodes in the graph, $A$ the number of edges, $U$ the maximal capacity of an edge in the graph, and $W$ the maximal costs of an edge in the graph. Then, my learning materials claim:

The maximal costs at the beginning can be no more than $AUW$
The augmentation along one negative cycle reduces the costs by at least one unit
The lower bound for the minimal costs is 0, because we don't allow negative costs
Each negative cycle can be found in $O(VA)$

And they follow from it that the algorithm's complexity is $O(V^2AUW)$. I understand the logic behind each of the claims, but think that the complexity is different. Specifically, the maximal number of augmentations is given by one unit of flow per augmentation, taking the costs from $AUW$ to zero, giving us a maximum of $AUW$ augmentations. We need to discover a negative cycle for each, so we multiply the maximal number of augmentations by the time needed to discover a cycle ($VA$) and arrive at $O(A^2VUW)$ for the algorithm.

Could this be an error in the learning materials (this is a text provided by the professor, not a student's notes from the course), or is my logic wrong?


texts: How to get this upper bound on worst-case heaps?

texts:
I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$
T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1)
$$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Update:

Trying to explain in more detail what I don't understand. As far as I know/remember for given $n$ that somehow measures how large is the input of an algorithm the worst case analysis is "choose among all the possible instances of size $n$ the one that would give you the worst case execution cost"

Following this direction, to me is not particular clear how for given $n$ we can be sure that the left subtree has $\frac{2n}{3}$ nodes, it is ok when the value $n$ is such that the distribution of nodes is such that half of the last level is full, while the other one is empty. In the proof for cost bounding I would differently.

I would distinguish two cases :

The tree has height $h$ and is complete, i.e. the total number of nodes is $2^{h+1} - 1$, I would also explain that it is possible to build in such case an heap such that starting from the root key it is possible to push down such key until it reach a leaf, how much is the cost in such case? it is exactly $h = ln_2(n+1) - 1 = O(ln \;n)$.
The tree has height $h$ but it is not complete, given the heap structure the left-most leaf is at height $h$. As done in point 1 I would explain it is possible to build a tree such that the root would be pushed down always in the left branch. How much is the cost in this case? Given that $n > 2^{h} - 1$ we have that $h < ln_2(n+1) = O(ln(n))$.

I don't think is difficult to build a particular example for both 1. and 2.
I also don't really see the point of "completing a tree" for computing the worst case cost, I can understand this operation can make the analysis easier, but for what I know about worst case analysis (assuming it is correct) it doesn't sounds correct to me.


texts: Can intersection of non-context-free languages be context-free?

texts: For two languages over the same alphabet that are not context-free, can their intersection be context-free, Or does at least one of them have to be context-free?


texts: Uniform convergence for a class of finite dimension

texts:
The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. Convergence of Stochastic Processes. Springer, 1984. However, I have trouble finding the proof. Anyone knows a reference?
Let $\Phi$ be a distribution over $\mathcal{X}$. With probability $1-\delta$ over $x_1,...,x_N\sim\Phi$, for all $a\in\mathcal{A}$ it holds that $\left|\frac{1}{N}\sum\limits_{i=1}^na(x_i)-\mathbb{E}_{x\sim\Phi} a(x)\right|\le\sqrt{\frac{2d}{N}\ln\frac{eN}{d}}+\sqrt{\frac{1}{2N}\ln\frac{2}{\delta}}$
where $\mathcal{A}: \mathcal{X} \rightarrow \mathbb{R}$ is a set of real-valued functions and $d$ is the psuedo-dimensionof $\mathcal{A}$.


texts: Is machine learning and AI all about pattern recognition?

texts: I realized that machine learning and AI is mostly about spamming the auto correlation and cross correlations from mathematics and combining them with memory arrays. Is it right? What do you think about this?


texts: Given two identical DOM trees find same node in tree B

texts:
So for the question 'Given two identical DOM trees, and an element in one tree, find the same element in the second tree'.
I can solve it in two ways -

Start at the given element and traverse up to the root of tree A - save the path and then follow the path down the second tree to the element.

Start at the root and traverse both trees at the same time using breadth first search - once I find nodeA in tree A return the current node in treeB.

The complexity for the second approach will be O(N) as worst case I could end up going through every node in the tree to find the element.
For the first approach is the complexity simply O(P) where P is the length of the path from the given node to the root? At most I will go up P nodes and then down P nodes in treeB and 2P ~= P. I heard someone say it's Log(N) but I'm not sure how that could be.


texts:
Say I have 2 carts on an infinite railroad, each cart is initially under a lamp.
There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between them is D, but its not known.
Each cart has a processing unit, both will execute a copy of the same program once the whole system is "initiated".

The task: to write a code in pseudo-code, which will make the 2 carts collide.

Restrictions:
The following commands can be used:

  move left/right *insert_number_here* steps //each movement takes 1 clock cycle, meaning that "move left C steps takes C clock cycles
  if underlamp *put_instruction_here* //if the cart is under a lamp
  goto *number_of_line_here*
  stop

Variables, loops and not (!) are usable.

the given solution is:

  for i=1 to infinity:

  go left i steps.
  if underlamp stop.
  go right i steps.

Now, I need a hint to help me make a simple improvement to the algorithm that is given in the trivial solution, so when the distance between the lamps is D, the total number of steps of both carts will be a first order polynomial function of D.

My lecturer gave the following solution, and told me to improve the given code using a different idea.
This is his solution:

  go right.
  go right.
  go left.
  if underlamp goto 6.
  goto 1.
  go right.
  goto 6.

My improvement of the given code, but I'm not sure that in this one, the total number of steps is a first order polynomial function of D.

  for i=1 to infinity:

  go right i steps.
  if underlamp goto 4.
  go left.

  4.for j=1 to infinity:

  go right j steps.


texts: Finding the lowest-weight negative cycle in a weighted digraph

texts:
Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?


texts: Repeated linear programming with similar (not identical) problems

texts:
I have multiple linear programming problems of the form:
$$
Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0
$$
Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a more efficient solution than solving each problem from scratch?
Currently I'm using scipy's linprog but the performance is too slow given the amount of problems (thousands). I was wondering if there's a way to make this feasible with some smart preprocessing.
I've tried searching using terms such as "repeated linear programming", "repeated simplex" etc., but to no avail.


texts:
At work we build large machines, these get deconstructed, placed i crates and shipped away to the client.
Now we are just guessing how many trucks we need and how we lay the crates out to fit as many of them inside a truck.

For example:

We have a truck and want to load 8 crates of equal size into it. There are 2 possible "solutions" to this problem.

But here you can see that the second option is better in space used (all pallets fit).

Now the real question. Is there a algorithme out there that can do this, even with irregular crates (meaning diffrent in size). Or do i need to invent one myself?

EDIT: Some more details:

The crates can vary in dimensions. But are always rectacles or squares.

The crate dimensions voor in the form of an Excel file where width height and lenght are defined.


texts:
LOOP:LW    R1,0(R2)
     ADDI  R1,R1,#1
     SW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     BNEZ  R4, LOOP

If we want to move an instruction into a branch delay slot what will be that instruction and the schedule of the instructions?

In the solution they have brought SW R1,0(R2) into the branch delay slot like this:

LOOP:LW    R1,0(R2)
     ADDI  R2,R2,#4
     SUB   R4,R3,R2
     ADDI  R1,R1,#1
     BNEZ  R4, LOOP
     SW    R1,0(R2)

But according to me it will change the meaning of the program since R2 will be incremented by 4 before storing the word. Can anyone clear this?


texts: Probability that the word is of language using N-Grams

texts:
Some programm should allow users to identify the word language probability. All i have is some statistics - the frequency of using bigrams and trigrams in most of texts of some languages.

Totally i have

Top English bigrams       Top Spanish bigrams   ...
th                         de                    ...
he                         es                    ...
in                         en                    ...
er                         el                    ...
...                        ...                   ...

So how can i calculate the probability, that the word is of language?

`


texts: Is there an efficient way to cluster a graph according to Jaccard similarity?

texts:
Is there an efficient way to cluster nodes in a graph using Jaccard similarity such that each cluster has at least k nodes?

Jaccard similarity between nodes i and j: Let S be the set of neighbours of i and T be the set of neighbours of j. Then, the similarity between i and j is given by  $\frac{|(S \cap T)|}{|(S \cup T)|}$.


texts: Which all nodes will qualify as an ancestor?

texts:
I was going through the fundamentals of tree structure and the definition for ancestor is as follows:

  A node u is an ancestor of v if there is a path from u to v.

Consider the node 11. Is node 2 (not the root, the other one on the left) an ancestor of node 11? It is strictly not a grandparent of 11, however, there does exist a path between these nodes. This is confusing to me, because this would also imply that the sibling nodes (5) of 11 would qualify as an ancestor.


texts: Heuristic for making set of indexes in an array/matrix with generating functions/patterns

texts:
I am trying to find a lead on how to solve or find a heuristic the following kind of problem:

Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a given form, generate indices for the 1 entries in the array/matrix.

The looping function/pattern is as followings:

index = (z_offset + z_i) * z_stride +
        (y_offset + y_i) * y_stride +
        (x_offset + x_i) * x_stride

The values are generated with loops.

indices = []

for z_i in range(0, z_dim)
    for y_i in range(0, y_dim)
        for x_i in range(0, x_dim)
            index = (z_offset + z_i) * z_stride +
                    (y_offset + y_i) * y_stride +
                    (x_offset + x_i) * x_stride
            indices.append(index)

For example the indices for the 1s in this array can be generated with these parameters:

x_dim = 3, y_dim = 1, z_dim = 2
x_stride = 1, y_stride = 3, z_stride = 6
x_offset = y_offset = z_offset = 0

[1 1 1
 0 0 0
 1 1 1]

These are the array entries indices and the indices made by the loop:

[0 1 2
 3 4 5
 6 7 8]

[0 1 2 6 7 8]

Notice if thought of as a matrix the size of the matrix doesn't matter because the indices would still be the same. e.g.

[1 1 1 0
 0 0 1 1
 1 0 0 0]

[0 1 2 3
 4 5 6 7
 8 9 10 11]

Another example, now with offsets:

x_dim = 2, y_dim = 2, z_dim = 3
x_stride = 1, y_stride = 2, z_stride = 7
x_offset = 1, y_offset = z_offset = 0

[0 1 1 1 1
 0 0 1 1 1
 1 0 0 0 0]

So now the problem is the reverse and in two parts.  If you are given a set of indices (e.g. [0 1 2 6 7 8]) find the parameters for this function (x_dim, y_dim, z_dim, x_stride, y_stride, z_stride, x_offset, y_offset, z_offset)

Find an exact or heuristic way to do that would be great but the second part of the problem is more difficult. If the indices do not map exactly to a single set of parameters then find a set of parameters for N functions (e.g. (x_dim_0, y_dim_0, ... z_offset_0), (x_dim_1, y_dim_1, ... z_offset_1), ... (x_dim_N, y_dim_N, ... z_offset_N)

Ideally there would be a solution for finding the minimum number of parameter sets but a heuristic that just finds a solution would be good too. Also, Ideally the parameter sets would be orthogonal (i.e. none of the indicies one set produces are the same as the indices another set produces)

EDIT: To clarify the inputs to the algorithm is the array of incides (e.g. [3 4 5 9 10 11]). I'd like to have an approach for an array of indices of any size but I imagine practically the max size would be around 64*64*5 ~= 20000 and typically 32*32*3 3072 but maybe as small as 8*8*3 = 192

If anybody has any insight how to approach or solve this problem any help would be appreciated!


texts: Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous

texts:
Prove that the following grammar is unambiguous:
$$X \to  aX | Y$$
$$Y \to Yab | b$$

I know that I must prove that the strings produced by this grammar have only one parse tree, but how can I do this?


texts: How to convert NFA with null moves to NFA without null moves?

texts:
I am converting NFA with $\varepsilon$-moves  to the NFA without  $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have to be repeated from $q_i$. And if the $q_j$ is a final state, then $q_i$ will also be a final state.

But, if $q_j$ does not contain any transition, i.e., there are no edges starting from $q_j$, then what has to be done?


texts: Paging - access less than a page of memory

texts:
I'm having a bit of trouble understanding how less than a page of memory can be used.

From what I understand, memory is given out in page size chunks - say pages are 4096 bytes, and 4 bytes are requested in a program via malloc, can less than a size of a page be allocated? Or is the rest of the memory in the page wasted?


texts:
Two problems: Given a known table (boolean or int), convert it to a function that returns the same value using only simple operations (and, or, xor, sum...). For example:

bool table1[] = {0,1} converted to fun (int index) {return index;}

bool table2[] = {0,1,1,0} converted to fun (int index) {return index ^ (index>>1);}

int table3[] = {4,5,7} converted to fun(int index) {return index+4+(index>>1);}


texts: Differences between substitution and rewriting?

texts:
I am continuing with my self-study of formal languages.

Given two alphabets $\Sigma$ and $\Delta$, a string substitution is a mapping from $\Sigma$ to $\mathcal P(\Delta^*)$, which induces a mapping from $\Sigma^*$ to $\mathcal P(\Delta^*)$.

In case that a string substitution is a string homomorphism, it  is a mapping from $\Sigma$ to $\Delta^*$, which induces a mapping from $\Sigma^*$ to $ \Delta^*$.

A rewriting system, however, seems to be a relation on $\Sigma^* \times \Delta^*$.

So I wonder if the main difference between rewriting and substitution is that rewriting is a relation, which might not be a mapping, while substitution is a mapping? Thanks.


texts:
I'm working on semi automatic texture segmentation using level set and gabor feature vector described by Manjunath und Ma [1]. I consider their feature representation is better than others since I can get good result on several images but somehow performs really bad on other images data. So I guess there's something wrong with my understanding.

They describe that the feature vectors consist of $\mu_{mn}$ (mean) and $\sigma_{mn}$ (standard deviation). I use scale $S = 4$ and orientation $K = 6$, thus my feature vector will be 48 dimension (4 * 6 * 2 = 48):

$f = \{  \mu_{00}, \sigma_{00}, \mu_{01}, \sigma_{01}, \mu_{02}...\mu_{35}, \sigma_{35}  \} \tag1$

I am confused with their equation:

$W(x, y) = \int I(x_1,y_1)g_{mn} * (x - x_1, y - y_1) dx_1 dy_1 \tag2$

$\mu_{mn} = \int \int |W_{mn}(x,y)|dxdy \tag3$

$\sigma_{mn} = \sqrt{ \int \int (|W_{mn}(x,y) - \mu_{mn}|)^2 dxdy } \tag4$

So my first question is: are $\mu$ and $\sigma$ simply mean and average? So far, I just average every pixel value of the magnitude to obtain $\mu$ and compute the standard deviation to obtain $\sigma$.

After I compute the feature vector, I need to do distance measure between two vectors $f_i$ and $f_j$

$d(i, j) = \sum_{}^{m}\sum_{}^{n} d_{mn}(i, j) \tag5$

$d_{mn}(i, j) = |\frac{\mu_{mn}^i - \mu_{mn}^j}{\alpha(\mu_{mn})}|  + |\frac{\sigma_{mn}^i - \sigma_{mn}^j}{\alpha(\sigma_{mn})}| \tag6$

I'm really puzzled with $\alpha(\mu_{mn})$ and $\alpha(\sigma_{mn})$ ? What are they? I have tried to calculate 48 standard deviations from $ (1)$

$\alpha = \{ \alpha(\mu_{00}), \alpha(\sigma_{00}), \alpha(\mu_{01}), \alpha(\sigma_{01}), \alpha(\mu_{02})...\alpha(\mu_{35}), \alpha(\sigma_{35}) )\} \tag7$

and use it to calculate the distance function but I'm not convinced with my calculation since it seems not better than simple euclidean distance.

Texture Features for Browsing and Retrieval of Image Data by B.S. Manjunath and W.Y. Ma (1996)


texts: How would I calculate the cache hit rate (ratio) percentage?

texts:
If I am correct the hit rate formula is:
Hit ratio = successful hits / total requests... so would the question below be formatted as such:
I tried 4 entries / 8 memory accesses but that wasn't right any ideas?
Given a simple cache with 4 entries. Following the sequential memory accesses: 10000,10001,10011,10100,10000,10010,10000,10001, the cache hit rate is ___%
My interpretation of 'hits' tell me if I'm wrong!
Grab the last 3 digits of the first '4 entries' allowed:
000 (was hit 2x)
001 (was hit 1x)
011 (not hit)
100 (not hit)
the last four is...
000 (HIT x1)
010 (MISS)
000 (HIT x2)
001 (HIT x1)
Since there are a total of '8 entries' each entry is worth 12.5% (out of 100%)
So I tried calculating with the above info: 2 of the entries were hit so 12.5 * 2 = 25%.
Would this be correct?


texts: Linear programming vs integer linear programming

texts:
Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$.  Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$.
Suppose that there is a feasible solution $x \in \mathbb{R}^n$ to the linear programming problem where $x_1 = 1$.  Also, suppose there exists a solution to the corresponding integer linear program, i.e., there exists $x' \in \{0,1\}^n$ such that $Ax' \le b$.  Are we guaranteed that there exists a solution with $x'_1=1$, i.e., there exists $x' \in \{0,1\}^n$ such that $Ax' \le b$ and $x'_1=1$?
To put it another way: if we solve the linear program associated with a zero-or-one ILP instance, and find that one of the variables gets assigned to 1 in some solution to the linear program, does it follow that there exists a solution to the ILP instance where we set that variable to 1?
I am skeptical but could not find either a proof or a counterexample.


texts: NL Completeness Log space reduction $PATH$ to $EQ_{DFA}$

texts:
Let $$PATH = \{(G, s, t) | \exists \text{ a directed path from $s$ to $t$ in $G$}\},$$
$$EQ_{DFA} = \{(M_1, M_2) | \text{DFA $M_1$ and $M_2$ over the same alphabet are equivalent}\}.$$
Is there a log space reduction from $PATH$ to $EQ_{DFA}$?

My attempt was to first show that there exists a DFA that accepts a string iff $M_1$ and $M_2$ do. At this point, I am unsure how to reduce the first problem to the second.


texts: NP-hardness of Capacitated Minimum Spanning Tree and Price Collecting Steiner Tree on dag/tree

texts:
I am thinking about the NP-completeness of two graph problems on different graph structures.

For example:

The Capacitated Minimum Spanning Tree for graph is NP-hard. However, is the problem still NP-hard for DAG or tree?
For Price Collecting Steiner Tree, it's NP-hard for graph. What about for DAG and tree?


texts: Winnow versus Perceptron - Why adding irrelevant features increases L2(X) but not L∞(X)?

texts:
I saw here: http://www.cs.cmu.edu/~ninamf/ML11/lect0906.pdf

Intuitively, if “n” is large but most features are irrelevant (i.e. target is sparse but examples are dense), then Winnow is better because adding irrelevant features increases L2(X) but not L∞(X). On the other hand, if the target is dense and examples are sparse, then Perceptron is better.

Why adding irrelevant features increases L2(X) but not L∞(X)?


texts: There is a theorem that says if a language is regular, its reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?


texts: Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?

texts:
This answer seems incorrect to me:
Which NP-Complete problem has the fastest known algorithm?
The fastest solution for one NP-Complete problem should be the fastest solution for all NP-Complete problems.
Why?
Can any NP-complete problem be reduced to any other NP-Complete problem in polynomial time?
So, finding some super-optimal exponential time solution, $O(1.27k + nk)$, should be able to be applied to all NP-Complete problems. In other words, the most optimal solution is the same for all NP-Complete problems.


texts: Karatsuba Multiplication with n/3 division of large number

texts:
I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts.

Now I'm trying to understand how the multiplication will take place when a number is divided into three parts instead of two.

I tried to solve the math but only came up with more number of multiplications than in Karatsuba.

Can someone help me out with this problem?


texts: How can I do an optimization problem that involves finding a sequence?

texts:
The problem I am trying to solve is to find the fastest way to produce an total amount of something. There are several different producers that each have a different production and cost (based on the number of the item that is already owned) which can be purchased during production.

For example, assume that the goal is to produce 1000 units total (including the amount spent on buying new producers), and the three producers that can be bought $A$, $B$, and $C$, have productions and base costs of $1$ per second and $20$, $7$ per second and $50$, and $14$ per second and $100$, respectively. Buying a producer multiples the price of the next producer of the same type by 1.1 (so, for example, buying an $A$ for the base price of 20 means the next $A$ will cost $1.1 \cdot 20 = 22$, and the next $1.1 \cdot 22 = 24.2$, et cetera). When a producer is bought, the price of the produced is subtracted from the current units produced, but not the total production (so if you have 30 units, and you buy an A, you now have 10 units left). Selling a producer returns half of the units used to purchase it, and reduces the cost by 1.1 times (so if the cost was at 24.2, it would go down to 22). By starting with 1 $A$, what is shortest amount of time to produce 1000 units and in what order should you purchase producers?

The shortest time is 68 seconds, buying producers in the following order:
A,B,B,B,C,C,C,C.

My first solution was simply to try all the different sequences, then determine the one that will be the fastest after $n$ purchases, but, naturally, this was very slow.
My second solution was to try a greedy search where I just look for the best solution in terms of time at every step.
My third solution was to try a search where I used the increased in production as the score for each sequence, and backtrack to earlier solutions if any of them had better scores.

Are there any other problems or generalizations I can make to find an optimal (or near optimal solution faster)?


texts: Convert tree with recursive relationship to parent-child tree

texts:
Background: I have a .yaml file which holds around >3000 elements. The elements are related to each other through a recursive relationship. I want to create a tree view containing those items. A good algorithm is needed, since I also have other .yaml files with more items.

Question: How can I convert a tree with recursive relationship between those elements to a parent-child tree.

FROM:

TO:

There are more elemtens like id=2 which have no parent anymore and the height of the resulting tree might vary.

What I tried so far:

Find the lowest childen which is not parent of some other element
Save those childen into a list/vector
Iterate over this list/vector and connect parents which results into a linked list

But now I have the problem that I have to rotate the tree in some way in order to receive a tree from which I can create my tree view. I hope there is a better solution than I came up with.

Edit 1:
If you parse such a .yaml file you will get a tree structure where each node has a key with a value or not. You can see in the picture that for example '2' is a key without a value and one childen with the name 'name'. The child 'name' itself has two children with the key 'en' and value 'Europe'.

You can say that those children are attributes from the item with the id '2' but still you will get a tree structure.

Now I want to make a tree which has in its first node the item with id '2' and all its 'attributes' and then in its child node the item with the id '3' and a sibling node with id '1'; and the item with the id '3' has a child node with id '4'.

Edit 2:
What did I mean with 'recursive relationship':
The term might be confusing and inappropiate in this situation. In a relational database model you can have a relationship from one relation (table) to itself. You call this a 'recursive relation'. The table would then have the columns 'id' and 'name' and 'parentID'.

I was hoping that this term makes my problem more clear because the 'parentID' does not refer to another .yaml file or some different id. However, it refers to some 'top' node (except the single root node) within the same file ('top'-node means image 1: node with id=1, id=2, id=3, id=4). If you think of those 'top' nodes being a tuple within a relational database you can say that the 'parentID' refers to another tuple which is related to it as parent.

The general rule, which I can think of is: I have a broken tree where actual parents/children are all siblings: (image 1 and image 4)

node with id=1 is sibling of node with id=2, id=3, id=4
node with id=2 is sibling of node with id=1, id=3, id=4
node with id=3 is sibling of node with id=1, id=2, id=4
node with id=4 is sibling of node with id=1, id=2, id=3

The child node 'parentID' of all those siblings tells me which node should be the parent node. Now I want to create a tree with the correct child-parent relation: (image 2)

node id=1 becomes a children of node id=2
node id=4 becomes a children of node id=3
node id=3 becomes a children of node id=2
node id=2 has no 'parentID' and so won't change its place

So, the algorithm has to:

Find the parentID of one 'top' node (maybe with DFS)
Find the correct parent (maybe iterate over all 'top' nodes and stop when id=parentID)
Make the node (1.) the child of node (2.) (Maybe linked list or something else)
Repeat until I went through all 'top' nodes

This algorithm could be good but there is the fact that there is no order within the file. So, at step (2.) I also have to go through all child nodes since my parent could already became a child of some other node. See image 1:

'top'-node with id=1 becomes a children of 'top'-node with id=2
'top'-node with id=2 has no parent (parentID=0) and won't change its place
'top'-node with id=3 becomes a children of 'top'-node with id=2
'top'-node with id=4 has now to become a children of node id=3


texts:
I have stumbled upon this problem online:

  Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... > A(j) for which the sum of elements in the subsequence is maximized.

Now my solution is so:
I assume that the sequence is stored in an array.
We need 2 arrays under the original array, one is a flag array A and the other is a real number array B.

Take the first element as the subsequence we are searching for, put a 1 under it in A, and put the value of the element in it's index in B (which is right under it's index in A).
Go to the next element.
If it isn't negative, put a 1 under it in A, and put the sum of that element and the element before him in B.
If it's negative, put a 0 under it in A, and go to the next element, starting a new subsequence.

The complexity is O(n) time because I run on the whole sequence once.

Example:

Sequence: 4 33 -24 3 4 2 -5 6 19 -11 32 40 -30 5 6
Array A:  1  1   0 1 1 1  0 1  1   0  1  1   0 1 1
Array B:  4 37  13 3 7 9  4 6 19   8 32 70  40 5 11

My question is: is that the wanted solution? and does it really run in O(n) time?


texts: Why do TPTP Performance plots look like this?

texts:
CASC is the premier Automated Theorem Prover competition performed annually at the Conference on Automated Deduction (CADE). The 2017 event has finished on the 9th of August this year.

During this conference provers are faced with a set of problems and a time limit of 5 minutes (300 seconds) per problem.
When the competition is over, the timings for each problem are taken to produce performance plots.

Here we see the results from the general first order formulas (FOF) division. 11 ATP systems participated, Vampire 4.2 was the winner in this division having solved over 450 problems from the set.

It  is clear from this plot that the timings for each prover were independently sorted in increasing order and plotted over the same axes.

What is puzzling is the shape of the graph: for most provers most of the problems were really easy (solved within 50 seconds) and only a small proportion of problems were difficult yet solvable within the time limit (i.e. about 5% for Vampire 4.2 and less than 10% for Vampire 4.0, the 2016 winner). On the remaining problems (there were 500 problems altogether) the prover failed. Is there an intuitively simple explanation of why the difficulty distribution is so skewed towards "easy" problems not for one but for all provers?


texts: A task-scheduling problem as a matroid (CLRS book)

texts:
I don't understand very well section 16.5 of the 3rd edition of the famous Introduction to Algorithms book, known as CLRS. It defines the problem of scheduling unit-time tasks with deadlines and penalties for a single processor with the following inputs:

a set $S = {a_{1}, a_{2}, ..., a_{n}}$ of $n$ unit-time tasks
a set of $n$ integer deadlines ${d_{1}, d_{2}, ..., d_{n}}$ such that each $d_{i}$ satisfies $1 \leq d_{i} \leq n$ and task $a_i$ is supposed to finish by time $d_i$
a set of of $n$ nonnegative weights or penalties ${w_{1}, w_{2}, ..., w_{n}}$, such that we incur a penalty of $w_i$ if task $a_i$ is not finished by time $d_i$, and we incur no penalty if a task finished by its deadline.

And the following goal:

We wish to find a schedule for S that minimizes the total penalty incurred for
missed deadlines.

NOTE: I'm aware that there are other posts here about similar problems (scheduling unit-time tasks with profit etc.), but I'm trying to understand this particular explanation, on the CLRS book.
So, I'll get now to the point. On the same page (444), where it explains the core idea, the book talks about the early-first form and the canonical form, without mentioning the penalties anymore: it talks exclusively about the deadlines (I'm not going to copy the whole text, I'm assuming that who answers the question owns the book).
My first question: because the whole reasoning does not mention penalties, it looks like to me it will work only if all the penalties are equal, which would be a different problem. I'm probably missing something here. But what? No matter how you order the tasks based on deadlines, you cannot possibly minimize the penalties without taking them into account. In other words, even if you hit 99/100 deadlines and missed the deadline for that one single task, its penalty might be bigger than the penalties of all the other tasks combined. I don't understand CRLS's logic, in this particular case.
My second question: on the next page (445), CLRS mentions the penalties in one place:

The problem of minimizing the sum of the penalties of the late tasks is the same
as the problem of maximizing the sum of the penalties of the early tasks. The
following theorem thus ensures that we can use the greedy algorithm to find an
independent set A of tasks with the maximum total penalty.

And after that it mentions theorem 16.13 claiming substantially that $(S, I)$ is a matroid.
I believe I understand that, it makes sense. But, how can we determine in the first place the subset of the early tasks without taking into account the actual values of each $w_i$ penalty? In my understanding, that's not possible. I wouldn't dare claiming there's a mistake in the CLRS book, but that's my only theory at the moment. Very likely I'm wrong, but I cannot figure out why. On page 444, it mentions twice "monotonically increasing deadlines" but never anything like "monotonically decreasing penalties".
On the other side, I've done some research and I've read about variations of this problem with profits instead of penalties. I've understood that the tasks need to be ordered by monotonically decreasing profit. After doing that, we put each task as close to its deadline as possible, and move left only (= early) when the slot is already taken. That makes completely sense, because the profit is taken into account. If we consider penalties as negative profits, shouldn't the same logic apply? But, even with a different logic, how can we ignore the $w_i$ values?


texts:
$L=\{\left<M\right> \ | \ M $ is a TM s.t. $M$ does not accept any string starting with a '1' $\}$.
   Assume the alphabet to be $\Sigma = \{0,1\}$.

By Rice's theorem $L$ is undecidable. I managed to "prove" that $L$ is decidable. So can someone point out the error in my proof. To keep things clean I ignore the empty string since it can easily be dealt with as a special case.

We can write $$L = \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] \neq 1\}$$
$$ = \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] = 0 \}$$
To get $\overline{L}$ we need to negate the condition in $L$. Hence
$$\overline{L}= \{\left<M\right> \ | \ w\in \Sigma^*, \ w \in L(M) \implies w[0] = 1 \}$$

We have
$$\exists \ w\in \Sigma^* \text{ such that } w\in L(M) \text{ and } w[0] = 1 \iff \left<M\right>\not \in L \iff \left<M\right> \in \overline{L}$$
We can construct a recognizer for $\overline{L}$ by searching for such a $w$

$R=$ 'on input $\left<M\right>$ where $M$ is a valid TM:

for $w \in \Sigma^*$:
$\ \ $if $M(w) =$ accept
$\ \ \ \ $if $w[0]=1$ then accept'

So $\overline{L}$ is recognizable. Similarly we have

$$\exists \ w\in \Sigma^* \text{ such that } w\in L(M) \text{ and } w[0] = 0 \iff \left<M\right>\not \in \overline{L} \iff \left<M\right> \in L$$
We can construct a recognizer for $L$ by searching for such a $w$

$R'=$ 'on input $\left<M\right>$ where $M$ is a valid TM:

for $w \in \Sigma^*$:
$\ \ $if $M(w) =$ accept
$\ \ \ \ $if $w[0]=0$ then accept'

So $L$ is also recognizable, this means $L$ is decidable.


texts: What is meant by "give pattern of a regular expression"

texts:
I have an alphabet $A = \{b,B\}$ and I'm asked to write down the pattern of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. Does it want me to give the possible patterns that can be formed with $b$ and $B$? But then surely the question would not have been phrased the way it is.

I'm just confused about what I need to do here and what is expected of the answer. If anyone could give an example it would be very helpful.

Note: This is not the original question, I changed and simplified it.


texts: Why do we need to convert binary numbers into hexadecimal, octal and decimal?

texts: Computer reads binary. Now my question is, what is the use of hexadecimal, octal and decimal? Do Computers understand or can read hexadecimal, octal and decimal? This question remains a mystery for me. Why memory locations use hexadecimal, it should be in binary right? Or is it because it is a binary and by time we read its memory location, the computer converts its memory location from binary into hexadecimal for us to make it readable?


texts: Peer grading design - choosing a graph, to get accurate rankings/ratings

texts:
Background. I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose which is better and how much better it is.  e.g., the slider might look something like this:

A---X-B

Based on the results of the peer grading, essays are ranked and the teacher will then grade the top X% and bottom X% and scores for all essays will be automatically calculated based on this.  I have already come up with methods for doing this ranking/scoring process; that part works well.

My question. How should I select which pairs of essays to give to students?

Simulations suggest we need an essay to be peer-graded at least 3 times, to get an accurate ranking.  Thus, each essay should appear in at least 3 of the pairs that are presented for peer grading.

We can think of this as a graph problem.  Think of the essays as nodes.  Each edge represents a pair of essays that are presented during the peer grading process.  The accuracy results above suggest that the degree of each node (or of most nodes) should be at least 3.  What sort of graph should I use?  How should I generate the graph to be used during peer grading?

One challenge is that if you have clusters in the graph, this will skew the peer-gradings.  For example, we wouldn't want to have high-quality essays peer-graded mostly against high-quality essays, because that would skew the results of the peer grading.

What would you recommend?

I think this problem could be modelled with a undirected graph using something like the following:

Start by taking the node with the least degree and link it with the next least
Continue until your average degree is at least 3
Maximise node connectivity
Minimise number of cliques

Is this a good approach? If not what would you recommend instead?


texts: Combinational Logic - Need help with proof by rewrite

texts:
In my Computer Logic class we were assigned the following problem:

  Complete a truth table that has $3$ inputs $(A, B,C)$ and one output
  $(F)$.   $F$ is        asserted whenever $B$ or $C$ are asserted, but
  deasserted if both $B$ and $C$ are asserted.  $F$ is asserted whenever $A$ is
  asserted and $C$ is deasserted.  $F$ is deasserted in all other cases.

After which we are supposed to

  Determine the sum-of-products equation for $F$.  Show the terms instead
  of the minterm abbreviations (show $ABC$ instead of m7).

Finally, we are supposed to:

  Prove that $F$ from question $2$ is equivalent to $F = BC' + B'C + AC'$
  using proof by rewrite.  HINT: remember the uniting law is the key to
  minimization.

Here is what I have:

1)

A    B    C    F
0    0    0    0
0    0    1    1
0    1    0    1
0    1    1    0
1    0    0    1
1    0    1    1
1    1    0    1
1    1    1    1

2) $F = A'B'C + A'BC' + AB'C' + AB'C + ABC'$

Number three is what is throwing me. I am using the axioms of boolean algebra, such as the Uniting Law, but so far all I have been able to do is the following:

3)
    A’B’C + A’BC’ + AB’C’ + AB’C + ABC’ = BC’ + B’C + AC’

A’B’C + A’BC’ + AB’C’ + AB’C + ABC’

A’B’C + AB’C + A’BC’ + AB’C’  + ABC’            Commutative Law

B’C + A’BC’ + AB’C’ + ABC’                      Uniting Law

A’BC’ + ABC’ + B’C + AB’C’                      Commutative Law

BC’ + B’C + AB’C’                               Uniting Law

That's as far as I am able to get. Did I screw up the truth table, resulting in incorrect minterms, or did I miss something?

Appreciate the help!


texts: Finding minimal strongly connected graph

texts:
I have this question:
Given a strongly connected and directed graph $G = (V,E)$ with positive weights define $E(t)$ to be the group of edges whose weight is at most $t$. Find an algorithm that calculates the minimal $t$ such that $G(t) = (V,E(t))$ is strongly connected.

I thought about running Dijkstra $v$ times from every vertex and then all of the edges will be the minimal $t$ but I am not sure the time complexity is the best. Is there a better solution for this problem?


texts: Clarification on interplay between cache line size and read/write sizes

texts:
Say that you have cache lines with the size of 64 bytes and a set-associative or directly mapped cache. Let's also say that the word size is 8 bytes.

According to my understanding, we use a number of the most significant bits of a memory address in order to determine where in the cache to place the data. Am I correct in believing that, if I want load data starting from, for example, address 30, then all data starting from address 0 to 63 will be loaded into a cache line? Or will all data from address 30 to 93 be loaded?

If the former is the case, I assume that, if an instruction to load 16 bytes from address, say, 60, then this forces us to load two 64 byte cache lines (one line 0-63 and another 64-127). Is that correct or have I misunderstood something? Also, is this something that often occurs or are there reasons for why that isn't the case?


texts: How fast can we optimally cluster 1-D data?

texts:
K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) is minimized overall, i.e. the clusters as as "tight" as possible.

While NP-hard in the general case, I know it is $\text{PTIME}$-tractable if the points are on a line.

What is the best known upper bound on the time complexity of optimal clustering for the 1-dimensional case?

Note: Lower bounds are also interesting, but less so.


texts: How to solve a knapsack problem with increased weight limit?

texts:
Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the other has a weight limit of $W'=2W$. Assume that we have an optimal algorithm $\texttt{OPT}$ that solves the knapsack problem.

Let $O$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the first bin (that has a weight limit of $W$) and to the set of items $P$. Also, let $O'$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the second bin (that has a weight limit of $W'=2W$) and to the same set of items $P$.

Can we compare $O$ and $O'$?

I guessed that $$O'\leq 2O.$$


texts:
From my recitation class, I have the following exercise:

  $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$

  The above grammar is ambiguous.

  Make an unambiguous grammar which produce same language as the above.

  In the new grammar, $a$ has priority over $b$ and $b$ has priority over $m$.
  Also $m$ is associative.

Can you explain what the phrases

"has priority over" and
"$m$ is associative"

mean?


texts:
I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it.  I used to think that you could detect an infinite loop by meeting these four conditions:

arrive at the same state as you were in previously
with the same top symbol as you had last time
without consuming anything on the stack, and
without consuming any input.

...but this appears to actually be untrue for nondeterministic PDAs.  Consider this machine:

It accepts the empty string, but it matches all of my infinite-loop detecting criteria in the first state before it can do so.

The following version even contains infinite paths to accepting the empty string:

I am coding a NPDA simulator in Scheme, and while I am happy to accept that the halting problem is solvable for a PDA, I am clearly wrong about how it is accomplished.  How can it actually be done?


texts: Difference Between $n^{\Omega{(1)}}$ and $\Omega{(n)}$

texts: I am not sure about the difference between $n^{\Omega(1)}$ and $\Omega(n)$. It seems to me that the only difference is that $n^{\Omega(1)}$ can contain some sublinear functions, i.e., $n^{\frac{1}{2}}$, which is not the case for $\Omega{(n)}$. Is there any other differences between these two notations?


texts: Finding the minimal path from S to T that visit all vertices

texts:
So I have a complete and directed graph with weights.
I wish to find the shortest path from S to T that visits all other vertices in the graph at least once.
Another important piece of information I might have negative weights but i don have negative cycles.

I found this problem very close to the salesman problem but soon enough I found out that it won't be of any help. That's because the salesman problem does not define destination vertex.

Any ideas will be highly appreciated.


texts: "Flow layouts" inside a GUI -- how do I come up with a good algorithm?

texts:
I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode):

int rowHeight = 0;
RECT rect = parent.getClientRect();
POINT pos = rect.position;  // Start at top-left corner, row by row

foreach (Window child in parent.children)
{
    // POINT is a tuple of: (x, y)
    // SIZE is a tuple of: (width, height)
    // RECT is a tuple of: (left, top, right, bottom)
    RECT proposed1 = RECT(rect.left + pos.x, rect.top + pos.y, rect.right, rect.bottom),
         proposed2 = RECT(rect.left, rect.top + pos.y + rowHeight, rect.right, rect.bottom);
    SIZE size1 = child.getPreferredSize(proposed1),
         size2 = child.getPreferredSize(proposed2);
    if (size1.width <= proposed1.width)
    {
        child.put(proposed1);  // same row
        pos.x += size1.width;
        rowHeight = max(rowHeight, size1.height);
    }
    else
    {
        child.put(proposed2);  // new row
        pos.x = rect.left;
        pos.y += rowHeight;
        rowHeight = size2.height;
    }
}

In other words, the algorithm is very simple:
The layout manager asks every component, "is the remaining portion of the row enough for you?" and, if the component says "no, my width is too long", it places the component on the next row instead.

There are two major problems with this approach:

This algorithm results in very long, thin components, because it is essentially greedy with the width of each component -- if a component wants the whole row, it will use the whole row (ugly), even if it could use a smaller width (but larger height).
It only works if you already know what the parent's size is -- but you might not! Instead, you might simply have a restriction, "the parent's size must be between these two dimensions", but the rest might be open-ended.

I am, however, at a loss of how to come up with a better algorithm -- how do I figure out what would be a good size to to 'propose' to the component?   And even when I figure that out, what should I try to optimize, exactly? (The area, the width, the aspect ratio, the number of components on the screen, or something else?)

Any ideas on how I should approach this problem?


texts: When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

texts:
In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that

$\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$,

where $K(\sigma)\downarrow$ means that $K$ halts on $\sigma$, $\sigma$ being a binary string. $K$ denotes the prefix-free Kolmogorov complexity.

When does $K$ halt? I think it only halts on a finite number of inputs, since the classical proof on non-computability of the Kolmogorov complexity gives an upper bound on the domain of $K$. But then, the finite set of inputs on which $K$ halts can be chosen arbitrary (one just needs to store the finite number of complexities in the source code).

So is this sum well-defined? In other words, is the domain of $K$ well defined?


texts:
I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight constraints.

Maximize $\sum_{j=1}^nx_j$

subject to $\sum_{j=1}^nw_{ij}x_j\leq W_i$ for $1\leq i\leq m$

and $x_i=0,1$.

This is a special case of multidimensional knapsack. I've looked at the list of knapsack problems, but the only one with uniform value is not multidimensional but instead wants the sum of weights to be exactly $W$. Is there some reference for the version I described?


texts: Random unbalanced bipartite graphs are good small set expanders

texts:
My question is about small set expansion properties of random unbalanced bipartite graphs.

Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$ an $(n,m,d,\delta)$-expander if the graph has $n$ left vertices, $m$ right vertices, every left vertex has degree $d$, and for every subset $S$ of left vertices having size at most $\delta n$, we have $|\mathcal{N}(S)|>0.75 d|S|$. Here $\mathcal{N}(S)$ denotes the set of neighbours of $S$.

Consider a random $d$-left regular graph, where the neighbourhood of each left vertex $i$ is a random subset $V_i$ of $d$ vertices on the right, and the $V_i$'s are chosen independently of each other. For small $\delta$ independent of $n$, and $d=O(\log(1/\delta))$ and $m=O(n\delta\log (1/\delta))$, a random $d$-left regular graph is an $(n,m,d,\delta)$-expander with high probability for sufficiently large $n$. We can prove this by computing $Pr[\mathcal{N}(S)\subset T]$ for $S,T$ with $|T|=0.75 d|S|-1$ and then taking a union bound over possible $S,T$ pairs.

If we force $d$ to be a constant independent of $n$, and $m$ to grow linearly with $n$ while having $m<n$, what are the best parameters we can hope for (in the sense of having small $d$ and $m$)? Is the above existence result order-optimal? If we are also interested in obtaining the best constants (and not just order optimality), what is known?

Also, is there a different proof/proof technique of existence of $(n,O(n\delta\log(1/\delta)), O(\log(1/\delta)),\delta)$ expanders? I tried to compute the expected size of the neighbourhood of $S$ and concentrate it using Chernoff-type bounds, but the parameters so obtained are worse.


texts: How does an inverted index reduce storage requirements?

texts:
In p. 7 of the book "Introduction to Information Retrieval" (by Manning et al), the authors explain how, given a collection of text documents, an inverted index is built by tokenizing,  then sorting the (term, docID) pairs, merging multiple occurrences of the same pairs, and the pairs for each term are grouped into a posting list.  It is then mentioned that "Because a term generally occurs in a number of documents, this data organization already reduces the storage requirements of the index."  My question is: how are the storage requirements reduced?  It seems to me that if a term occurs in $k$ documents, then these $k$ documents' ID's must all be mentioned in the linked list for this term.
If a term occurs multiple times in the same document, then because the inverted index mentions a  docID at most once in a term's list, there is a reduction in storage.  But this condition is different from the condition that a term occurs in multiple (distinct) documents.


texts: How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?

texts:
So the wikipedia page gives the following linear programs for max-flow, and the dual program :

While it is quite straight forward to see that the max-flow linear program indeed computes a maximum flow (every feasable solution is a flow, and every flow is a feasable solution), i couldn't find convincing proof that the dual of the max-flow linear program indeed is the LP of the min-cut problem.
An 'intuitive' proof is given on wikipedia, namely : $d_{uv}$ is 1 if the edge $(u,v)$ is counted in the cut and else $0$, $z_u$ is $1$ if $u$ is in the same side than $s$ in the cut, and $0$ if $u$ is in the same side of the cut than $t$
But that doesn't convince me a lot, mainly why should all the variables be integers, while we don't have integer conditions ?
And in general, do you have a convincing proof that the dual of the max-flow LP indeed is the LP formulation for min-cut ?
Edit : Ok i found a proof here http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf , however it only gives a probabilistic way to build the cut from the variables assignement of the LP.


texts: Proving that $L=\{ \langle M \rangle \colon L(M)=L(M)^R \}$ is undecidable

texts:
I'm trying to show that
$L=\{ \langle M \rangle \colon L(M)=L(M)^R\}$ is undecidable, but I don't even know where to begin. Google wasn't much of a help, maybe because it's hard describing the language in words. Any hints?


texts: How to prove that there is a function index t so that t³ + t + 1 is an index of the same function?

texts:
I would like to prove $\exists t\phi_t = \phi_{t^3+t+1}$ where $\phi_0,\phi_1,\phi_2,...$ are sequence of all of the partially computable function.

$\phi_t = \phi_{t^3+t+1}$ only if $t = t^3+t+1$ and it means $t=-1$! and there is no program with number $-1$!


texts: Loading a word from a byte addressed cache

texts:
In a cache with byte addressing, the byte you want to load is selected using the block offset. But what if I execute a LW instruction and don't want a single byte but a full 32 bit word?

Is there some logic that selects whether you don't look at the block offset and just load the whole word (when you use a "load word" instruction) or you look at the block offset to choose the right byte (when you use a "load byte" instruction)?


texts: Why can't we reduce register automata to symbolic automata?

texts:
When considering automata, they are normally considered over finite alphabets. The following are two types of automata that can handle words over infinite alphabets (definitions included for clarity).

The symbols $\triangleright$ and $\triangleleft$, appended to the beginning and end of the word respectively, are delimiters and are not in $\Sigma$. That is, the automata process words of the form w = $\triangleright$v$\triangleleft$ where v $\in$ $\Sigma^*$.

A k-register automaton $\mathcal A$ over $\Sigma$ is a 5-tuple (Q, $q_0$, F, $\tau_0$, P) where:

Q is a finite set of states;
$q_0$ $\in$ Q is the initial (or starting) state;
F $\subseteq$ Q is the set of final (or accepting) states;
$\tau_0$ : $\{0,1,...,k\}$ $\to$ $\Sigma$ $\cup$ $\{\triangleright,\triangleleft\}$ is the initial register assignment; and,
P is a finite set of transitions of the form ($i$, $q$) $\to$ ($q'$, $d$) or $q$ $\to$ ($q'$, $i$, $d$) for $i$ $\in$ $\{0,1,...,k\}$, $q$, $q'$ $\in$ Q and $d$ $\in$  $\{Stay, Left, Right\}$.

A symbolic finite automaton (SFA) $\mathcal M$ is a 5-tuple ($\mathcal A$, Q, $q_0$, F, $\Delta$) where:

$\mathcal A$ is an effective Boolean Algebra (the alphabet);
Q is a finite set of states;
$q_0$ $\in$ Q is the initial (or starting) state;
F $\subseteq$ Q is the set of final (or accepting) states; and,
$\Delta$ $\subseteq$ Q $\times$ $\Psi_{\mathcal A}$ $\times$ Q is a finite set of transitions.

Research has shown that for register automata, equivalence is not decidable but in symbolic automata, it is. My question is why? These two automata types work with similar results, so why is it that we can't reduce one to the other?

Something tells me this is a very simple problem but I can't seem to find an answer anywhere, so thank you for any help! :)

My current thoughts are to do with the fact that SFA require their alphabet to be an effective boolean algebra, whereas RA work on anything and so their alphabets dont have to follow the rules of a Boolean algebra. I dont know how to correctly formulate this idea into anything useful though.


texts:
As mentioned in Lambda Calculus - Computerphile,

  Alonzo Church's method is functional where a function as a blackbox,
  takes an input, processes, and produces an output, and Turing machines
  have internal state.

First, I would like to know what does it exactly mean by functional and state-based?
Are they the same as the terms stateful and stateless?
And how are they related, similar and different from one another?

Not quite sure if this question is to be asked here or in Stackoverflow.

Ref: https://www.revolvy.com/main/index.php?s=State+(computer+science)
Ref: Learning fundamental differences between functional programming and Object Oriented Programming


texts: Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

texts:
Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗.

This is what I have so far

Let N be some language that is known to be context-free but not regular (for example, {a^nb^n | n ≥ 0}). Consider the language L = N#Σ∗ ∪ Σ∗#L(G), where # is some symbol that is not in L(G) or N.

Where to? I just know my prof is going to put this on my exam :s.


texts: Smallest DFA that accepts given strings and rejects other given strings

texts:
Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^*\setminus B$?

In other words, $A$ represents a set of positive examples.  Every string in $A$ needs to be accepted by the DFA.  $B$ represents a set of negative examples.  No string in $B$ should be accepted by the DFA.

Is there a way to solve this, perhaps using DFA minimization techniques?  I could imagine creating a DFA-like automaton that has three kinds of states: accept states, reject states, and "don't-care" states (any input that ends in a "don't-care" state can be either accepted or rejected).  But can we then find a way to minimize this to an ordinary DFA?

You could think of this as the problem of learning a DFA, given positive and negative examples.

This is inspired by  Is regex golf NP-Complete?, which asks a similar questions for regexps instead of DFAs.


texts: Difference between logic, fuzzy logic, probabilistic logic, quantum logic?

texts: I am not sure if the names of these logics are right, but I saw that you can generalize logic with probability theory. Then I found 3 ways of reasoning with probabilistic/smooth logic, Fuzzy, Bayes/probabilistic and quantum. Can someone explain what are the major differences and expressiveness of such logics? Are they useful in normal logic?


texts: How can I determine the start non-terminal of a CFG?

texts:
Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint).

$A ::= x|y|z$
$B ::= a|b|c$
...
$N ::= l|m|k$

Further suppose that I cannot simply merge these production rules together as they are used in different parts of the grammar.
How can I hence determine or rather choose, the start non-terminal $S$, for purposes of $LL(1)$ parsing?
Thanks


texts: Limited number of calls to a black box for finding longest path in graph given an access to oracle

texts:
I'm given a black box that on graph $G = (V,E)$ and integer $0< K<|V|$ outputs $1$ iff there is a simple path of length greater than $K$ in $G$. I want to find the actual edges of the longest path in $G$ using as few calls to my black box as possible.

What I've come up with thus far is using the same method as when binary searching, i.e. first calling my black box with $K = |V|/2$ and so forth, but I'm not really sure what to do once I've found the $K_{max}$.. I'd really want to go in and change the black box to output the actual edges but that's impossible.

Edit: So I can delete any edge $e_i$ from $G$ and see if my black box still returns 1 (once I've found the maximal length path) - if it still returns 1 i know $e_i$ isn't part of the longest path, and if it returns 0 I know $e_i$ is part of the longest path(s) and I append it to my data structure holding the longest path. But what should I do if there are several paths of the maximum length? It feels as if I will return all the edges of all the longest paths and not just one specific.


texts: Amortized time cost of insertion into an Array list

texts: A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied over into the newly resized array 1, 2, 4, ... , n number of copies. What then is the sum of this sequence? To answer that we see that the sequence written backwards is n + n/2 + n/4 + ... + 1. Until here I understand what has been said. Here is where my confusion starts, how is this sequence roughly equal to 2n? How do we know this? Once we settle that we can say that n insertions take O(2n) time, but from that how do we deduce that the amortized time for each insertion is O(1).


texts: Sliding Window Dictionary String Matching

texts:
Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every pattern in $\Pi$ is contained in the substring $s[i:i+k]$.

Can this be solved in linear- or near-linear-time? It can of course be solved in quadratic time $O(|s| |\Pi| + \sum |\pi_i|)$ using KMP or Aho-Corasick plus post-processing.

The motivation for this problem is finding matches for a topic (represented by the set of patterns) in a text. In that context it actually makes sense to require the matches to be non-overlapping so I'm also interested in that case, but it might be easier to start with the relaxed version.

I would also be interested in generalizations of the problem that allow for approximate matches of some kind, eg, only requiring a threshold on the size of the subset of matching patterns, allowing matches within given edit distance, or something using hidden Markov models or general probabilistic graphical models. I would be surprised if any such generalization can be solved in subquadratic time though.


texts: Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum

texts: There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is it true for any problem on graph which has such a greedy algorithm.


texts:
I'm still trying to get the hang of lambda calculus:
I completed simplified some of these already but am lost on the last two. I did so far:
\begin{align*}
    (\lambda x.x)y &\to y\\
    (\lambda x.y)x &\to x
\end{align*}

However, I'm not sure how to simplify these two:

\begin{gather*}
(\lambda x.x y)(\lambda y.y z)\\
(\lambda x.x y)(\lambda a.a b) p
\end{gather*}
They are a little bit similar, but I'm not sure how to simplify these expressions.


texts: PDA for all non-palindromic strings of even length

texts:
I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$.

I already turned it in, but I know I had it wrong and it's driving me insane that I can't figure out this construction.

I tried a Cartesian product construction of the following languages and then deselected the accepting states of $L_2$, but I obviously did it wrong:

$L_1 = \{x \mid x \text{ is even}\}$

$L_2 = \{xx^R\}$, where $x^R$ denotes $x$ reversed.

I kept running into a problem where it would still accept because Palindromes are even and I was basically accepting all even numbers.


texts: How does one efficiently produce all binary sequences with an equal number of 0's and 1's?

texts:
A binary sequence of length $n$ is just an ordered sequence $x_1,\ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary tree structure in the following way: the root is "empty", but each left child corresponds to the addition of $0$ to the existing string and each right child to a $1$. Now, each binary sequence is simply a path of length $n+1$ starting at the root and terminating at a leaf.

Here's my question:

  Can we do better if we only want to generate all binary strings of length $2n$ which have precisely $n$ zeros and $n$ ones?

By "can we do better", I mean we should have lower complexity than the silly algorithm which first builds the entire tree above and then tries to find those paths with an equal number of "left" and "right" edges.


texts: Designing CFG that accepts $a^n b^m c^p$ where $n=m+p+2$

texts:
I have generated the CFG of $a^n b^m c^p$ where $m = n+p+2$:

$S \rightarrow ASC \mid \varepsilon$
$A \rightarrow aAb \mid \varepsilon$
$C \rightarrow bCc \mid \varepsilon$

I have been trying $a^n b^m c^p$ where $n=m+p+2$ but cannot figure out how to represent $n=m+p+2$.
Any hint would really be appreciated.


texts: Are there repositories of automatically generated (spam) webpages?

texts:
I'm interested to see if I can use machine learning/network analysis methods to automatically detect automatically generated (spam) webpages.  I'm particularly interested in webpages that look structurally like a non-spam website, but on closer inspection are total rubbish.

If I want to test a method, I'd need some way of accessing (or generating) these webpages.

  Question: Where can I access automatically generated (spam) webpages?

Here's a sample of the kind of webpage I'm thinking about:

Image source


texts: Algorithm for finding optimal branch points

texts:
I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd like to minimize the amount of duplicate processing required. For example, if variations occur at step B, I could run step A one for all results before "branching" at step B (see #2 below). Similarly, I could branch again at step D if additional variations on step D are indicated (see #3 below).

1) Base Process:

input --> A --> B --> C --> D --> E --> result

2) Modification of Step B:

input --> A --> B1 --> C --> D --> E --> result1
                B2 --> C --> D --> E --> result2

3) Modification of Steps B and D:

input --> A --> B1 --> C --> D1 --> E --> result1
                             D2 --> E --> result2
                B2 --> C --> D1 --> E --> result3
                             D2 --> E --> result4

Is there a simple algorithm to determine the the common process steps and the branch points as in #3 given a base flow as in #1 and a list of steps to change, e.g.

Variation  StepB  StepD
   1         1      1
   2         1      2
   3         2      1
   4         2      2

The above example is simple but there could be hundreds of variations modifying dozens of different steps in actual usage.


texts: Use Dijkstra to find negative cycles in a graph

texts:
I will state the problem:

  Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph.

So, I saw the runtime, and I immediately said we need to use Dijsktra's implementation with a fibonacci heap.
I suggested the following:

  Run dijkstra, and mark the distances array as $d$. -- $O(|E| + |V|log|V|)$
  Do relax on each edge -- $O(|E|)$
  For each edge $<u,v> \in E$: -- $O(|E|)$

  3.1 if ( $d[v] < d[u] + w(<u,v>)$), report "negative cycle".
  report "No negative cycles"

Would this work?


texts: How to show that a language is strictly context sensitive

texts:
During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that

$L =  \{a^nb^nc^n \mid n > 0\}$

Could you help me to find the answer providing a detailed solution?

My approach:

I know that a language is strictly of type $n$ if there isn't a type-$j$-grammar ($j > n$) that can generate it.

So i wonder if i can apply the Pumping Lemma for Context Free Languages to prove that.


texts: What should I read before tackling Michael Huth's Logic in Computer Science: Modelling and Reasoning about Systems?

texts: I have to read Logic in Computer Science: Modelling and Reasoning about Systems by M. Huth and M. Ryan for a class next semester. However Amazon reviews say it's hard to read unless you're an advanced student and I'm very new to computer science. Is there any other book I may read before I approach this one that would make it easier to understand?


texts: Selection of parameters for genetic algorithm

texts:
How can one select the proper number of parameters for a genetic algorithm to model a given system?

For example, say you want to optimize production of cars, and you have 1,000 measurements of hourly efficiency at various tasks for each of 1,000 different employees.  So, you have 1,000,000 data points.  Most of these are likely to be weakly correlated to the overall efficiency of your factory, but not so weakly that you can say they are irrelevant with statistical confidence.  How do you go about picking inputs for your GA so that you don't have 1,000,000+ degrees of freedom, resulting in very slow convergence or no convergence at all?

Specifically, what are the algorithms one could use to pre-select or selectively eliminate features?

One approach I have used myself in this scenario is to evolve the parameter selection itself, so I might have parents like {a,b,c}, {b,d,e,q,x,y,z}, and so on. I would then mutate the children to add or drop features. This works well for a few dozen features. But the problem is that it is inefficient if there is a large number of degrees of freedom. In that case, you are looking at 10^n combinations (in the example above, 10^1,000,000), which makes some pre-filtering of features critical to get any kind of useful performance.


texts: Efficient Algorithms for Complex Networks

texts:
Most standard works on random graphs focus on $G_{n,p}$ and random regular graphs. However, such models are far from a good abstraction to describe the types of networks that one typically encounters in the real world.
There are several simple models that mimic the behavior of real-world graphs, sometimes called Complex Networks.
There are many graph problems that become easier in the setting of $G_{n,p}$, such as finding a Hamiltonian path, finding a perfect matching, etc. I am sure that similar work has been done for random complex networks, but I haven't been able to find a good book or survey paper on the subject. I must be using the wrong terminology.
I would be grateful if someone could point me towards something like that, or tell me what the subject of efficient algorithms for complex networks is called in the literature.


texts: Use machine learning algorithms data structure to store information (memory)

texts:
DISCLAIMER : I'm pretty new to machine learning field, so forgive me
  if my questions are somehow naive ... I already searched on Internet
  about this topic and find nothing interesting so I am asking here ....

I wonder if a ML algorithm can be consider as a way to store data ?
There is programs that "contains" thousands of decimal of PI (e.g. https://www.quora.com/What-is-the-smallest-C-program-generating-pi-without-using-the-math-library) : in some way it's a "compressed" version of the first thousands decimal of PI, right ?

In the same way ML (e.g. Deep Neural Net) seems to store information. Can we mesure how many bits is stored in a Deep Neural Net ? Can we use ML  algorithms data structure to compress information and retrieve it later (even if it's not 100% accurate) ? ...

Is there (not too technical ) papers that discuss these possibilities ?

Thanks :)


texts: How does a computer compute negative(-) and positive(+) Infinity?

texts:
If we divide (1.0/0.0) we will get +Infinity and if we divide (-1.0/0.0) we will get -Infinity.

How does a computer calculate this value internally?


texts: Encoding of graphs as an input to neural nets

texts:
Given a directed graph $G=(V,E)$ with a node labelling function $l:V\rightarrow L$, how would you encode this best for a neural network?

If it simplifies the problem, we can add the following assumptions about $G$:

$|V|$ is of fixed size $n$.
Every node $v$ in $V$ has exactly two successors.
$l:V\rightarrow L$ is injective; in particular, instead of using node labels, a total ordering of the nodes would be good enough to "infer" the original graph labels.

What I'm trying to learn is a successor selection for every node $v$ in $V$; in other words, a map $m:V \rightarrow V$ with $m$ subset $E$.

Taking all assumptions into consideration, we more or less only have to encode $E$. Obviously, we could use a "two hot encoding" for every node $v$, resulting in a quadratic number of inputs, but is this the preferred way of going about it?

Thanks!


texts:
When should I call a definition recursive and when should I call it inductive?

I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like natural numbers, lists, trees, etc. as inductive whereas we refer to definitions of operations over objects like $+$ or $head$ or $leftchild$ as recursive.

Is this the correct way to distinguish these in programming languages theory?

Are there examples where using either would make sense?


texts:
There was a question connected with one of the video lecture lessons that I'm currently watching.

Let two trees be given - the original and the tree after the zig-zig step:

Calculate the cost of this operation.

Where it is: the sum of the ranks of the new tree (after the zig-zig step) minus the sum of the ranks of the source tree. Now pay attention to the root tops of the trees. - because their rank is equal, then we can delete them from equation

Now, we carry out the upper bound. r '(u) and r' (w) - they can be estimated as r '(v) in the initial tree (up to the zig-zig step) in the upper estimate - the vertices u and w are above the vertex v - therefore, when estimating from above with respect to the vertex v in the source tree - we simply consider the potential of the vertices r (u) and r (w) as r (v) with the opposite sign. As a result, we get the expression:

Now the question is: why does index 2 change to 3?

At first I thought that it was +1 as an accounting cost for the actual action, but it turned out that this +1 should be performed for each vertex - that breaks all the evidence - there it is explained later in the lecture and also how to avoid it, But now this is not about it , but why, if this is not +1 for the actual action, then where did the index 3 come from?

P.s : Further in the lecture, attention is not focused on this - therefore I ask.