texts: Write through and write back cache policies

texts:
There are Two Write Hit policies: Write Through  and Write back
There are Two Write miss policies: Write Allocate and No Write
Allocate
There are two memory access techniques: simultaneous and
hierarchical access

Can any gentleman PLEASE write formulas for different combinations ?

I am having very important competitive exam that can change my life, and i am struggling with these methods badly.

For instance one may consider following example and please show me relevant modification of this example.
Question : In a certain system the main memory access time is 100 ns. The cache is 10 time faster than the main memory and uses the write though protocol. If the hit ratio for read request is 0.92 and 85% of the memory requests generated by the CPU are for read, the remaining being for write; then the average time consideration both read and write requests is

a) 14.62ns

b) 348.47ns

c) 29.62ns

d) 296.2ns

PS:- I know meaning or working of all techniques but don't know how can i drive formulas.
Please do it, i really need that badly. It would be GREAT help.

Thnks in advance.


texts: Do Higher Order Functions provide more power to Functional Programming?

texts:
I've asked a similar question on cstheory.SE.

According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to the FP language would make the algorithm $\Omega(n)$.

Is there any equivalent relationship comparing a FP language with and without Higher Order Functions? Is it still Turing Complete? If it is, does the lack of Higher Order on FP makes the language less "powerful" or efficient?


texts: Robot follows a path near an obstacle without colliding

texts:
I have a problem that I would like to solve it. A robot have to move near an obstacle (e.g a wall) without colliding. He should also try to be always near the obstacle.
The following picture can help you to understand what I need to do:

In red is the wall
Black dots is the robot moving
The dashed line is the path of the robot

The robot doesn’t have any information about the wall. He has only a sensor that can tell him approximately what the distance to the wall is.
A perfect robot is a robot who can move within a distance of 1m to the wall.  The robot some times doesn’t respect that distance:

The distance can be sometimes  > 1m
The distance can be less often < 1m
The robot can collide but it should be very rare and it is better to
avoid it all the time.

Do you have a solution for this problem?
I am new to AI and there is a lot of material to read. So on which topic of AI should I concentrate to find a solution for this problem?


texts: Is the number of nodes in an ORBDD 2n + 2?

texts:
Wikipedia says that the number of nodes in a ORBDD (Order Reduced Binary Decision Diagrams) of order $x_1 < x_2 < \dots < x_{2n}$ is $2n + 2$.

But I can't find proof. Anyone?


texts:
I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. Since a cubic graph has a decomposition into edge-disjoint claws if and only if it is bipartite.

  What is the complexity of deciding the existence of decomposition of a cubic graph into vertex disjoint claws? Is it NP-complete?

In the former problem, we partition the edge set into edge-disjoint claws while in the later one we partition the vertex set into vertex-disjoint claws.


texts:
Let $G = (V, E)$ be a connected, undirected graph. Given a subset of distinct vertices $S = \{v_1, v_2, \ldots, v_n\} \subseteq V$, how can I find a forest in which each vertex $v \in V - S$ is connected to exactly one of the vertices of $S$ and is of minimum total length?
This is a problem from an algorithms book that I'm currently struggling with. I'm pretty sure the idea is to construct a graph $G'$ on which a minimum spanning tree algorithm could be used (but I might be wrong). I've thought about it for a while, and I'm not able to make much progress. Could someone please point me in the right direction?
I thought about only keeping edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't and running an MST algorithm, but I'm not entirely sure if this is correct.
Thanks


texts: How does an Operating System without kernel mode work?

texts:
Andrew S. Tanenbaum, in his book Modern Operating Systems (3rd Edition), states that the distinction between operating system software and normal (user mode) software can sometimes be blurred in embedded systems (which may not have a kernel mode).

  Can someone please describe more what an OS without a kernel mode looks
  like and how it works?

Thank you.


texts:
How to convert access control matrix to Bell-LaPadula. Can teach me step by step
What best way to control converting Bell-LaPadula Model lattice using Access Control Matrix

Matrix GIVEN

$\quad\quad\quad\quad$O1      O2      O3    O4
    S1      w       r       w     rw
    S2      rw                    r
    S3              w       w     r
    S4      w       w       w     r
    S5              rw      rw    r

convert to BLP lattice diagram


texts: Complexity of a particular integer knapsack version

texts:
I need to know if the following problem is $NP$-complete.

The data are as follows :

$n$, number of items
$\{s_{i}\}_{i \in \{1, \dots n\}}$, item sizes, sorted by ascending values.
$S$ knapsack capacity.
$T$ a lower bound on the value to be attained.

Now, for each $i \in \{1, \dots n\}, c_i = \log i $ is the value of item $i$.
The same item may be picked any number of times.

The question is : if we note for each $i \in \{1, \dots n\}$, $x_i \in \mathbb{N}$, the number of times item $i$ is picked, does a set of values for all $x_i$ exist such that :
$$
\forall i \in \{1, \dots n\}, x_i \in \mathbb{N},
$$

$$
\sum_{i=1}^{n} s_ix_i \leq S
$$
and
$$
\sum_{i=1}^{n} \log i \cdot x_i \geq T
$$
?

A reduction from the subset sum problem doesn't look straightforward.


texts: Shortest path in NL algorithm, need help to understand

texts:
https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

I'm checking those solution and i'm having trouble understanding the proof that shortest path belong to NL (2.a).

So being Shortest path = {(G=(V,E), k, s, t) | shortest path from s to t in G has length k}  and rk-1 being the number of vertices reachable in k-1 steps, the proposed algorithm is

d ← 0
flag ← FALSE
for all w ∈ V do
    p ← s
    for i ← 1 to k − 1 do
        non-deterministically pick a neighbor q of p
    if p = w then
        d ← d + 1
    if w = t reject
    if w is a neighbor of t then
    flag ← TRUE
if d < rk−1 reject
if flag then accept else reject

In a line it does "non-deterministically pick a neighbor q of p" but q it's never used. Where and how it's q used?


texts: Call stack is hard to maintain in my brain. What should I?

texts:
When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and notes when the height BST is high.
Question: What should I? Is it normal and should I practice more?


texts: Show that the language of all total Turing machines is neither r.e. nor co-r.e

texts:
I've been thinking about how to show this but I'm stuck.

I'm required to prove this:

  Show that the language $$\mathrm{TOT}= \{\langle M \rangle : M\text{ is a Turing Machine that halts with all inputs} \}$$ is not recursively enumerable nor its complement. ($\langle M \rangle$ is an encoded Turing Machine with only zeros and ones).

I think we have to proceed by contradiction, assuming that $\mathrm{TOT}$ is recursively enumerable, so there must be a Turing Machine that we will call $T$ such that it can process any possible encoding $\langle M \rangle$ of a TM $M$ and only accept those machines that halt with all inputs.

So in order to confirm that $\mathrm{TOT}$ is r.e., $T$ should be able to do this for every $M$ that halts with all inputs. My idea is to show that this is not possible because the set $\mathrm{TOT}$ is not countable, so maybe I can show this using the diagonalization argument, but I'm not sure.

So what is the correct way to prove this?

Thanks


texts: Classes of languages for which the language $\{a_1^n \cdots a_k^n \mid n \geq 0\}$ is in the language for $k$ but not $k+1$

texts:
In any introductory course on the theory of computing, one encounters the language
$$L_k = \{a_1^n \cdots a_k^n \mid n \geq 0\}$$
as a canonical (or at least pedagogical) counterexample for a language which is not regular ($k=2$) or context-free ($k=3$). The next jump is usually to the turing machine, where $L_k$ is in the class for all $k$.

Is there a (sensible, e.g. defined in some terms of generating grammar or recognizing automaton) hierarchy of classes of languages $\mathsf{COMP}_k$ so that $L_j \in \mathsf{COMP}_k$ for $j < k$ and $L_j \not\in \mathsf{COMP}_k$ for $j \geq k$? Ideally it would also hold generally that $\mathsf{COMP}_k \subset \mathsf{COMP}_{k+1}$. Or, perhaps, is this distinction of being able to recognize $L_k$ not important/fundamental once $k \geq 3$ (in whatever sense you want to interpret that question)?


texts: Minimize shipping cost based on weight and price constraints

texts:
I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows:

There is a limit on the max price of the combined package (say $15)
The cost of the package is determined using the following table:

If total weight of package is < 30 grams, cost is 7.5
If total weight of package is >= 30g and <80g, cost is 7.5 + (weight - 30)x0.075
If total weight of package is >= 80g, cost is 7.5 + (weight - 30)x0.055

There is no limitation on the number of packages these items can be combined into as long they remain under the total price threshold.

I looked at the knapsack problem, but there are 2 major differences between the knapsack problem and my problem:

One is that we are not maximizing the weight or price of the items combined, instead we want to minimize a calculated variable that can only be determined after the combination.
Also, there isn't a direct correlation between weight and shipping cost.


texts: Finding the number of squares by connected coordinates

texts:
If I have a list of lists as below ,

 [[1, 2], [3, 4], [1, 5], [2, 6], [4, 8], [5, 6], [6, 7],
 [7, 8], [6, 10], [7, 11], [8, 12], [10, 11],
 [10, 14], [12, 16], [14, 15], [15, 16]]

and

[[1, 2], [2, 3], [3, 4], [1, 5], [4, 8],
     [6, 7], [5, 9], [6, 10], [7, 11], [8, 12],
     [9, 13], [10, 11], [12, 16], [13, 14], [14, 15], [15, 16]]

The above 2 lists can be visualized as in the image, where each point is represented by a list.

I know there is a graph traversal where every visited node can be tracked as we traverse through the graph. But in this case, there is no direction mentioned.

How should I approach this problem? I am also interested in hints.


texts: How to tell if a spanning tree is a shortest-spanning tree of a DAG?

texts:
I know how to calculate the shortest paths from source s to all other reachable vertices in a DAG (with no negative weight on the edges)

By iterating the topological sort of the graph and relax each adjacent vertices. Which take O(V+E)

However - I'm required to determine if a certain spanning tree is the shortest-path tree of some directed (may be cyclic) graph in time O(E)

I've got a hint from my professor to use the algorithm to find shortest paths... but I fail to see how that helps me.
All I've gotten so far is just building the shortest-path tree and comparing it with the tree given and return true or false.


texts: Ant Colony optimisation for finding subsets with ~0 sum

texts:
I have a set A = [x1, x2...xn] where xi in R (real). I need to find all non intersecting subsets with subset sum ~0 (approximately equal to zero).

Since the set can have non zero real numbers, I have opted to use Ant Colony Optimisation for this problem. I have implemented this in python and the program tends to be a  bit slow (python dictionaries for the graph). It takes around 60 seconds for 100 ants for single iteration. The algorithm goes like this:

Create a graph with the whole list of real numbers (fully connected)
Initialise the graph edges with w0
Each vertex has an associated value
Initialise the position of ants at random nodes
Ants select next nodes based on edge weights
Once an ant completes tour - the sum of all vertex values > threshold 1 (1000000) or < threshold 2 (~0.1), the path weights are updated based on path sum and global path updates (pheromone evaporation) after this

The questions I have:

Is the usage of ACO relevant here?
How can I improve the speed of the implementation?


texts: Why comparison is dominant time consumption for comparison-based sorting algorithms?

texts:
Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption?   While I understand the standard analyses of asymptotical behavior of number of comparison operations, I don't quite understand why other costs of other types of operations are negligible.

[Edit 2014-08-26]

If I run the same mergesort implementation on two different computers (with possibly different architecture etc.), how to argue that running time of mergesort divided by the number of compares will approach (possibly different) constants as the problem size increases?


texts: What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?

texts:
For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$?

It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $L\in\mathcal{O}(\lg(n))$ or $L\in\mathcal{O}(\mathrm{polylog}(n))$?


texts: Determine whether given f is shortest path function

texts:
I have the following question:
Let $G = (V,E)$ be a directed graph  with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every other vertex, i.e $0\leq dist(s,v) < \infty$. Let $f\colon V \to \mathbb R$ a given function. Describe an algorithm that runs in $O(|V| + |E|)$ that determines wethter this given $f$ is the shortest path function from $s$, i.e $\forall v \in V :f(v)=dist(s,v)$.

What I thought about was to check for every $v \in V$  whether $f$ fulfill the two following demands:

$f(s)=0$
$f(v) \leq f(u) + w(uv)$ for all $u \in V$ and $uv \in E$

This runs in the proper complexity. I thought to prove it by showing that $f(v) \leq dist(s,v) \land f(v) \geq dist(u,v) \Rightarrow f(v) = dist(f,v)$

I proved that $f(v) \leq dist(s,v)$, but I am stuck at proving that $f(v) \geq dist(s,v)$.


texts: Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

texts:
I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, however basically the author explains that it's a translation of the classic pencil and paper method and the Knuth book is the one that provides all the details. I really want to understand the analysis but for some reason that I can't quite understand it is a bit strange in the exposition.

It firstly starts by saying that

  "a moment's reflection about the ordinary process of long division shows that the general problem breaks down into simpler steps, each of which is the division of an $n+1$-place dividend $u$ by an $n$ place integers $v$.

I of course agree with such intuition, but it's because I've been taught in that way, not because there's a proof. It shouldn't be hard to work out the why however since

$$
\begin{array}{l}
u = \sum_{j=0}^{m+n-1} u_j b^j \\
v = \sum_{j=0}^{n-1} v_j b^j
\end{array} \Rightarrow \frac{u}{v} = \frac{\sum_{j=0}^{m+n-1} u_j b^j}{v} =
\frac{\sum_{j=m-1}^{m+n-1} u_j b^j}{v} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \frac{\sum_{j=0}^{n} u_{j+m-1} b^{j+m-1}}{v} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} =
\frac{\sum_{j=0}^{n} u_{j+m-1} b^j}{v}b^{m-1} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \left(q_{m-1} + \frac{r_{m-1}}{v} \right)b^{m-1} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = q_{m-1}b^{m-1} + \frac{r_{m-1}b^{m-1} + \sum_{j=0}^{m-2} u_j b^j}{v}
$$
where $0 \leq r_{m-1} \leq v - 1$, using an induction argument I can show that I have always to do this (i.e. that the problem is to perform several iteration of dividing an $n+1$ digit number by an $n$ digit number. One key observation is that of course if
$$
0 \leq q_{m-1} \leq b - 1
$$
then $q_{m-1}$ represent the most significant digit of the division

Later the problem is stated as

  Let $u = (u_nu_{n-1} \ldots u_1 u_0)_b$ and $v = (v_{n-1} \ldots v_1
v_0)_b$ be nonnegative integers in radix-$b$ notation, where $u/v <
b$. Find an algorithm to determine $q = \left\lfloor u/v
\right\rfloor$.

From this point I have a problem (which is the object of my question). After the observation made that the condition $u/v < b$ is equivalent $(u_n \ldots u_1) < (v_{n-1} \ldots v_0)$ I would also observe that  $v_{n-1}$ is not necessaraly 0. It is later defined the quantity
$$
\hat{q} = \min \left( \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1}} \right\rfloor,b-1\right)
$$
Where is not actually stated any condition on $v_{n-1}$, which at least shouldn't be $0$. Then the author proves both theorems $A$ and $B$ which they make perfectly sense to me if $v_{n-1} \neq 0$.

One could argue that before the theorems it is said

  ...as long as $v_{n-1}$ is reasonably large...

However I think that this statement should be interpreted more like "we now show how much large $v_{n-1}$ has to be in order to..." So there's actually no assumption here, he wants to show that.

The question is...
Shouldn't basically the condition $v_{n-1} \neq 0$ be clearly stated?
I'm sure there's something subtle about the condition $u/v < b$ that I'm missing...

(I have other questions but I'll go through that later)


texts: Generating a adjacency matrix representing a DAG

texts:
Does anyone have a pointer to a resource or, even better, a tip to provide on how to efficiently generate a very large matrix representing a connected graph.

Graph can be randomly created although I would ideally generate a graph of desired size and topology similar to what one can do with JGraphT.

My general intent is to create a very large graph representation (billions of nodes and edges) in parallel by first generating an adjacency matrix to ensure connectedness and then create a representation (RDF, etc) in parallel.

Any further suggestions or alternative approaches are welcome.


texts: requirement for pumping lemma in regular language

texts:
I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not.

This is what I have understood so far though For a regular language $L$, there exists a $p > 0$ such that for all $w ∈ L$ where $|w| ≥ p$, there exists some split $w = vxu$, for which the following holds:

$|vx| ≤ p$

$|x| > 0$

$vx^iu ∈ L$ for all $i ≥ 0$

but what is the rationale behind the requirement of $|vx| ≤ p$ what happens if we drop that requirement??

thanks ahead


texts: $L$ is decidable. Prove that "similar" language is also decidable

texts:
Assume that $L$ is decidable. Is the following language decidable? $$ L' = \{w | \text{ there is } u \in L \text{ such that u and w are equal to at most two positions.}\}$$

For example, let $u=abcd$. The following words are equal to $u$ at most two positions: $\{aba, agg, ab, zzz, dsa, ...\}$, but not $\{ abc, zbcd \}$

My approach:

  A language is decidable iff some enumerator enumerates the language in
  lexicographic order.

I use above theorem.

So, $L$ is decidable. Therefore, let's take enumerator $E$ for it. Let We construct a $TM'$ for $L'$. Let enumerator $E$ be connected to $TM'$. For every input $w$ given to $TM'$ the $TM'$ compare it position by position with every string $v$ generated by $E$ in lexicographical order till $|v|\le|w|$
If number of the same positions $>2$ reject $w$. Otherwise, accept.

Ok?


texts: Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

texts:
I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is:
 $$q_{2} = 1q_{2} \cup 0q_{2}$$
What's the procedure to solve this form? Thanks in advance


texts:
I need to show that the following problem is in P:
$$\begin{align*}\text{HALF-2-SAT} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and there exists an assignment} \\
& \text{that satisfies at least half of the clauses} \}\end{align*}$$

I know that 2-SAT is in P, hence it got a decider and I wanted to use it for HALF-2-SAT but got stuck to find how to extract the right half of the clauses that will be satisfied in a polynomial way.

Is there an official way to choose half of the clauses that satisfy the formula?


texts: Find PDA for CFL = {x#y | |x| = |y| and x ≠ y}

texts:
I am studying push down automata.

When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, $L_2 = \{x\#y \mid|x| = |y|,x \neq y\}$, and make a CFG for $L_1$, but I don't know how to make a CFG for $L_2$, since $y$ is not a reverse string of $x$. How can I know the $i_\text{th}$ symbol is different?

Note this question is different from Show that { xy ∣ |x| = |y|, x ≠ y } is context-free since we have an additional separator $\#$.


texts:
Okay.I have problem about cache mapping. Here is the problem .

Memory size is 1 MB
Byte addresable
Cache block size is 16 Bytes.
Cache size is 64kb

Since memory is 1 mb=2**20 Bytes.
 So we need 20 bits for the one single address .
Since it is byte addressable and each block size is 16 bytes we need for 4 bits the offset
and for the index 64 KB/16 bytes is equal to 2 to the power 12so we need 12 bits for the index
So remain part goes to the tag and which is 20-(12+4) = 4 bits.

After that I have given address which is 32 bit long in hexadecimal. For example
0X66349068

My question is how to find the tag,index and offset from the above address?


texts: How does one use the Nerode-Myhill theorem to prove that a language is regular?

texts:
Showing that a language is not regular is straight-forward, because all one needs to do is find an infinite set of inputs which has an injective mapping to the set of equivalence classes which compose that language.

How does one show that the set of equivalence classes of $L$ is finite? For instance, how would one show that the simple language $L = \{s:  |s| \equiv 0 \mod 2\}$ has a finite number of equivalence classes?

I think that showing that there is a surjective mapping is not sufficient, because the image may still be of infinite size.


texts: Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set

texts:
I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start.
Also, I want to devise a Mont Carlo algorithm for this problem.
I would appreciate any help.
Thank you.


texts: Constructing deterministic PDA for not regular language

texts:
Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of the b’s and there are the same number of a’s as b's and arbitrarily many c’s that can be in front, behind or among the a’s and b’s.
Some words in L are: abc ccacaabcccbccbc

I know that the language is not regular but how can I find a deterministic PDA (in a drawing fashion) that accepts L?

Edit: So far I've ended up with this which takes care of having the same number of a's as b's and all a's come before all b's. However I cannot figure out how to account for the arbitrary amount of c's in-between b's. Any ideas?

Sorry for the horrible drawing in advance.


texts:
What is the difference between DeepFake and First Order Motion?
Is it the same or not?


texts: Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

texts:
I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let D represent the structure. D contains 3 elements of the type Number D's default values will be initialized to 1, 2 and 3.

$$D = [1, 2, 3]$$

If a Number that contains the value 5 is inserted into D, 3 will be pushed out, while 1 and 2 are shifted right.

$$D = [5, 1, 2]$$

The first thing that comes to mind would be an array, but the definition does not include the pushing behavior.


texts: I'm trying to understand DFAs is my DFA correct in this question if not why?

texts:
I have the following alphat {0,1}.

I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0}

This is the DFA I came up with.


texts: Given a sorted array with n integers, how to find the element that has no duplicates?

texts:
I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-conquer algorithm. I have noticed that n needs to be odd to satisfy my condition. I thought about doing this: divide my array in two parts from the mid, if from [0, mid] or [mid, end] I have odd number of elements then my elements is in that half. So, recursively divide also that subarray and so on.

How to decide which part of the array to look at first?
Does this solution take O(logn)?
Is there other effective approach?


texts: Is "super-exponential" a precise definition of algorithmic complexity?

texts:
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.

For instance, if an algorithm runs for $nC(n-1)$ steps, where $C(\cdot)$ is the Catalan number, is this algorithm super-exponential in $n$?


texts: Informed search with a lower-bound heuristic?

texts:
I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state.

However, what about when one only has a heuristic that never underestimates the minimum cost from a node to any goal state? (Also: is there a name for such a heuristic?)

What I am currently doing is as follows. I first find some path to a goal state (luckily in my case this is relatively trivial) and record its cost and path as the best cost and path. Then I do a depth-first search, with two modifications. One, I do not stop when I reach a goal state, instead updating the best cost found so far and record the path to get here. Two, anytime I find myself at a node where the sum of the cost to get here and the heuristic is greater than or equal to the best cost found so far, I backtrack. Then at the end I output the best path found.

(Two nice things about this: 1) it's guaranteed to return an optimal solution, 2) if interrupted it has a solution, albeit a suboptimal one)

I've been calling this "iterative shallowing" (as opposed to iterative deepening), but I have no clue as to the actual name.

So: is there a name for this? If so, what is it? Is there a name for a lower-bound heuristic? Is there a name for informed search algorithms using only a lower-bound heuristic?


texts: How to pick w for the Pumping lemma if the language has no clear pattern?

texts:
I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this example, but what do you set w to if there isn't a particular form.

The particular problem I'm trying to prove isn't regular:
The language is the set of strings that is composed of 60% or more As and Bs with the alphabet {A, B, C, D}

Because the form of the strings is indeterminate (i.e. it doesn't follow a pattern like a^i b^i, I'm not sure how to divide the strings into a w and x, y, z.


texts: NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

texts:
As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified in polynomial time. Let's say we have a problem $K$ in NP and we have a certificate $c_e$ obtained externally that proves a YES or NO result for $x$.
From my understanding of the proof implications, if we have a NTM which solves $K$ in polynomial time, this implies that there exists a verifier for $K$ which takes any certificate and says whether that specific certificate is a valid "solution" for if $x$ results in YES/NO. The proof involves the fact that the NTM generates its own certificate $c_n$ which the verifier then uses, but this has nothing to do with $c_e$ from what I see. From my understanding, the verifier should take any arbitrary certificate (including $c_e$) and verifies that it indeed leads to the answer. But instead, the verifier uses only the certificate $c_n$ created by the NTM to verify whether $x$ results in YES/NO. In other words, the verifier isn't able to check any arbitrary certificate - it's only able to check the one created by the NTM.
To rephrase in case I'm not making sense – constructing a verifier, in my interpretation, means this verifier can take any certificate and check whether it's a proof for $x$. But the equivalence proof has the verifier take a specific certificate $c_n$ created by the NTM and only checks whether that is a valid proof for $x$. So what makes the verifier able to  verify for any arbitrary certificate $c_e$?
I must be getting confused somewhere. Is there any point which labels my misunderstanding? I'd really like to fully grasp the intuition of the proof.


texts: Why to use moving statistics instead of population statistics in batch normalization implementation at inference?

texts:
Many (tensorflow) implementations of batch normalization seem to use moving statistics at its inference phase (R2RT, tf.contrib.layers.batch_norm).

But in the algorithm from the original paper, they use population statistics in the batch normalization function.

The thing is, pardon me, I don't understand why most of the implementations do not precisely follow the original algorithm.

The paper itself very briefly mentions about 'moving average' but does not give specific instructions for algorithm implementations.

Can somebody save me please?


texts: Standardisation Theorem versus Leftmost reduction Theorem

texts:
According to Chris Hankin in his book (Lambda Calculus a Guide for Computer Scientists). A reduction sequence $\sigma: M_0 \to^{\Delta_0} M_1 \to^{\Delta_1}M_2 \to^{\Delta_2}\ldots $ is a standard reduction if for any pair $(\Delta_i, \Delta_{i+1})$, $\Delta_{i+1}$ is not a residual of a redex to left of $\Delta_{i}$ relative to the given reduction from $M_{i}$ to $M_{i}$. The Standardization Theorem says that if a term $A$ $\beta$-reduces to $B$, then there is a standard path from $A$ to $B$. On the other hand,  in the leftmost strategy, outermost redex is always reduced first. The Leftmost Reduction Theorem says that if a term $A$ $\beta$-reduces to $B$, and $B$ is in $\beta$-normal form, then the leftmost strategy reaches $B$. My question is:

1- I'm not seeing the difference between the reductions Standardization and Leftmost, for me, it seems to say the same thing.

2- Why the Leftmost Reduction Theorem is a particular case of the standardization Theorem?


texts: Experimental Survey on Different Heuristics for Knapsack Problem

texts: I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!


texts: Minimum path between two vertices passing through a given set exactly once

texts: Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes $\mathrm{dist}(S, P_i) + \mathrm{dist}(D, P_i)$?  In addition, the overall path from $S$ to $D$ should contain only one node from the set $A$.  What is an efficient algorithm for this? I don't want to go with brute-force approach.


texts: what is definition of algorithm in computer science?

texts:
I have problems in writing algorithms before writing code for a particular program.

An algorithm is just like a recipe.

But when it comes to programming complex structures (like nested conditional statements and loops) in my code, I am not able to write one, and often get confused easily. How can I get over this thing?


texts: What is the initial state of DFA equivalent to an $\epsilon$-NFA?

texts:
I am unsure I expressed myself correctly.

Anyway, I want to figure out what is the initial state of an automata who had its epsilon transitions removed and who was determinised.

In my text book it is stated, that suppose A is NFA with $\epsilon$-moves, suppose $q_0$ its initial state. Then the initial state of the equivalent DFA is the E-closure of $q_0$.

Yet in one of the softwares recommended by one of my teachers, $\epsilon$-NFA to DFA algorithm  always puts the initial state as $q_0$ and not E-closure($q_0$).


texts: Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$?

texts:
I'm already guessing that the answer is no because we cannot know whether there is a class "in between" already known classes? Or can we?
I am very new to complexity theory.
Thanks for any answer in advance!
EDIT: Now that I think about it again, what I am asking is if SAT was in P, could we show that SAT could not be in any class less complex than P? Or could not be in any class that requires as much time complexity as P?


texts: You are given a graph of all the nodes and links between them. Each node has an associate value with it and each link contains the distance between the two nodes. Once you reach a node, your current value adds upon the value at the node. Once you collect the value at a node it is set to 0. Assuming you start at Node A and you must finish at Node B and you have a maximum distance you can travel, how do you find the optimal path to get from Node A to Node B while obtaining the highest value score?


texts: Returning all the combinations of a string using regex

texts:
Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches?

For example, if the string is abcd,

then the regex should return the matches:

a
ab
ac
ad
abc
abd
...
...
(16 matches)

I was trying this regex for the string abcd:

(?:.*?)|(?:.*)|(?:.*)|(?:.*)

But this is only returning 5 matches - Demo

Also, regex patterns like this are dependent on the length of the string to match.
Is there any universal generic pattern which is independent of the input string?


texts: Is reduction from Rudrata/Hamiltonian path to Rudrata/Hamiltonian cycle O(1)?

texts:
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, s and the target, t is O(1) time as this doesn't depend on the size of the graph. Algorithms by Dasgupta et al. says that the pre and post processing steps take polynomial time.

One last detail, crucial but typically easy to check, is that the pre- and postprocessing functions take time polynomial in the size of the instance
(G, s, t).

Since O(1) is polynomial time of order 0, is this reduction O(1)?


texts: Is the powerset of a regular set also a regular set?

texts:
If so, where can I find a proof of it? If not, is there a counterexample?

By powerset of a regular language I mean the set of all subsets of a regular language.

Thank you, Marcus.


texts:
I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements.
Is this new?  And if so, what should I do with it?

https://github.com/Frazer/hashSort

let hashSortNonUnique = (unsortedArray)=>{
  let myHash = {}
  let min = Infinity;
  let max = -Infinity;

  unsortedArray.forEach(val=>{
    myHash[val]=myHash[val]?myHash[val]+1:1;
    if(val>max) max = val;
    if(val<min) min = val;
  });

  let count = 0;

  for (let sorter = min; sorter <= max; sorter++) {
    let num = myHash[sorter];
    while(num--){
      unsortedArray[count]=sorter;
      count++;
    }
  }
  return unsortedArray;
}

let hashSortObjectsWithNonUniqueVals = (unsortedArray,valFunction)=>{
  let myHash = {}
  let min = Infinity;
  let max = -Infinity;

  unsortedArray.forEach(val=>{
    v= valFunction(val);
    myHash[v]=myHash[v]?myHash[v].push(val):[val];
    if(v>max) max = v;
    if(v<min) min = v;
  });

  let count = 0;

  for (let sorter = min; sorter <= max; sorter++) {
    let vals = myHash[sorter];
    for (let index = 0; index < vals.length; index++) {
      unsortedArray[count]= vals[index];
      count++;
    }
  }
  return unsortedArray;
}


texts: Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

texts:
Let $A[1..n]$ be an unsorted array, we want to find the $n/lgn$ intermidiate numbers in the array.

Namely the $(n/2)+1$ biggest number and the $(n/2) + 2$ biggest number and so on... until the $(n/2) + (n/lgn)$ biggrst number.

We are studing on the select algorithm and sortings.

I think it should go somehow with select algorithm as it has an efficiency of $\Theta(n)$

But its not that simple. As just making a loop will get us to \Theta(n^2)$

Just a remainder - the select algorithm compute nad finc the median of the medians in order to find the $i$ value in the array with run tie of $\Theta(n)$

Any suggestions?

Thank you.


texts:
Design the grammar for the following:
L = (a^n)w(w^r)(b^n) where n>=0 and w={a,b}


texts: How the website owner keep track of your times of access?

texts:
To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP each time we go online, don't we?
 Is there anyway to hack this?


texts: Are Huffman trees and optimal binary search trees for solving the same problems?

texts:
Huffman trees are used in a specific application - Huffman coding - for finding the minimum-expected-length binary-coding for a set of strings, with respect to a probability distribution over the string set.

Optimal binary search trees (as defined in CLRS's Introduction to Algorithms) are used for finding the optimal binary search tree for a set of elements, so that the expected look-up time is minimized, with respect to a probability distribution over the set.

Noticing how similar they are to each other, I have some questions

Is it correct that  the applications of Huffman trees are not limited to Huffman coding?

What kinds of problems can Huffman trees be used to solve?

Can Huffman trees be used for solving the same problems that optimal binary search trees can?

Can optimal BSTs be used for solving the same problems that Huffman trees can?
One difference I notice between Huffman trees and optimal binary
search trees is that

In Huffman trees, all the elements are stored in the leaves, so that a successful search always end up in a leaf.
In optimal binary search trees, not all the elements are stored in the leaves, and a successful search may end up in an internal node.

So if Huffman trees and optimal BSTs can both solve a problem, then
is the Huffman tree always higher than an optimal BST, and thus will
the Huffman tree take longer on average to look up an element?

Thanks.


texts: Implement opposite() method to tell if there are two opposite numbers, (x,-x)

texts:
Let a dictionary with the operations insert(), delete() and search(). Each one of them has time complexity of $O(logn)$. Implement (efficiently) opposite() operation which return true if there are two opposite numbers in the dictionary (i.e. $5$ and $(-5)$)

I advised to use another data structure.

I thought about a binary search tree. We maintain a binary search tree and for every insert() we also insert the item into the tree.

What do you think?


texts: How would one use "BUT" logic in a ternary logic computer in a practical way?

texts:
Using three valued logic one can define a multitude of ternary operations.  When dealing with 5:3:1[1] operations, its very easy to see how OR and AND work, but I'm confused as to how ternary BUT is supposed to be useful. As mentioned here in TriINTERCAL's[4] docs the truth table for ternary BUT is as follows:

BUT(True, True) = True
BUT(False, True) = False
BUT(False, False) = False
BUT(True, False) = False
BUT(Unknown, x) = Unknown   for all x

This is a 5:3:1 operation, as out of the 9 possible cases, 1 of those leads to True, 3 lead to False, and 5 to Unknown.

How could such an operation be used in practice (either on single trits[2] or multiple trytes[3])?

The individual who created the Tunguska ternary computer emulator claims that other people found BUT a useful operation coming from TriINTERCAL, even though the author of TriINTERCAL mentions that they don't seem to be useful.

[1]
5:3:1 operations are what you call binary ternary operations where the 9 possible values of the operations are split up like so among True, False, and Unknown, but not necisarily in that order.

[2]
A trit is a ternary bit. A trit holds the value 0,1,2, or False, Unknown, True.

[3]
A tryte is a ternary byte.  Though the value can vary, it is typically 6 trits (3^6 possible values = 729, so more than a byte).

[4]
TriINTERCAL is a programming language based off of INTERCAL that utilizes ternary logic instead of binary.


texts: Big O notation comparison with constant time

texts:
So,  I'm new to this whole asymptomatic notation with respect to algorithms. So say you have a $f(n) = 1/n$ and $g(n) = 1$,  would it be OK to say that $f(n)$ is not equal or is not an element of $O(g(n)) $?
 I say this because I'm actually drawing an analogy with another example.  Say in my second example $f(n) = n$ and $g(n) =n^2$ then I'm sure that $f(n)  = O(g(n))$.


texts: Reducing linear programming to positive linear programming

texts:
Suppose we have an oracle that solves problems of the form

\begin{align*}
\text{maximize} ~~ & c^T x
\\
\text{subject to} ~~ & A x = b, x\geq 0
\end{align*}

when $c\geq 0$ (all coefficients in the maximization target are non-negative).

Can it be used to efficiently solve general linear programs?

FAILED ATTEMPT #1: replace each variable $x_i$ that appears with a negative coefficient in $c^T x$, with another variable $y_i := - x_i$.
Unfortunately, this $y_i$ does not satisfy the non-negativity constraint.

FAILED ATTEMPT #2: Ensure that all elements in $b$ are non-positive (multiplying the equation by -1 if necessary). Then create the dual LP:

\begin{align*}
\text{maximize} ~~ & - b^T y
\\
\text{subject to} ~~ & A^T y \geq c
\end{align*}

Here, all the coefficients in the objective are non-negative. However, this form does not match the form that the oracle can solve, since the constraints are not equational constraints and the variables $y$ are unbounded.


texts: I thoroughly enjoyed my algorithms class but I felt that it lacked rigor. Most of the time I was able to intuitively understand why the algorithms presented worked and why they had the time complexity that was presented but I'd like to be able to prove such things. As such, I'd like a book that goes over lots of common algorithms and has a focus on proving the correctness and time complexity of the algorithms. Any good recommendations?


texts: Proving a PDA with CFG Transitions recognizes Context Free Languages

texts:
I'm working on a proof that deals with a modified PDA, which is identitical to a PDA, but with transitions: \begin{equation*}
a,b \to c
\end{equation*} where $a$ is a context free grammar, instead of just a symbol. The modified PDA then reads a prefix $w'$ of $w$, the suffix of the input stream, where $w' \in L(a)$.

I'm try to prove that the language recognized by this modified PDA is context free, but I'm really stuck. I have no idea how to even get started. If someone could point me in the right direction, I would really appreciate it.


texts: Weighted Activity Selection Problem with allowing shifting starting time

texts:
I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists.

In my case, I am allowed to shift the start time of activities in some extend while duration remains same. This will give me some flexibility and I might increase my utilization.

Example scenario is something like the following where all activities are supposed to be in interval (0-200):

(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 130 100
a6: 126 132 150

Without shifting flexibility, I would choose (a1, a3, a6) and thats it. On the other hand I have shifting flexibility to the left/right by at most t units for any task where t is given. In that case I might come up with this schedule and all tasks can be selected.

t: 5

a1: 8 10 120 (shifted -2 to left)
a2: 10 13 100
a3: 14 18 150
a4: 18 23 100 (shifted +4 to right)
a5: 115 125 100 (shifted -5 to left)
a6: 126 132 150

In my problem, I have more than enough room for each activity in the time domain. There are clusters of activities which overlaps and very big empty space where no activities and there comes another cluster of overlapping activities i.e a1, a2, a3 and a4 are let say cluster1 and a5 and a6 is cluster2. Each cluster can be expanded in time by shifting some of them to left and right. By doing that, I can select more activities than the original activity selection problem. However, I do not know how to decide which tasks to be shifted to left or right.

Are there any feasible solution to this problem?


texts: Min-eigenvalue bound for a random d-regular graph

texts:
I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In particular, I think $|\lambda_n| = O(\sqrt{d})$.)
Exercise 7 in [1] is to prove this fact, so it seems like there should be a simple proof. However, I cannot think of a reasonably simple proof or find one anywhere, despite a lot of searching. In [2], they prove that $\max\{|\lambda_2|, |\lambda_n|\} = o(d)$, but their proof is very complicated and only focused on the $\lambda_2$ part -- further indicating that there is some simple proof I'm missing for the $\lambda_n$ part.
My attempts always seem to come to proving something harder than we started, like, $\mathbb{E}[x_ix_j] \ge -o(1)/n$ for adjacent $i, j$ and any assignment $x$ to the vertices. I have no ideas that seem to actually move me forward, so even a pointer would be greatly appreciated.
[1] https://www.sumofsquares.org/public/lec02-1_maxcut.pdf
[2] https://www.researchgate.net/publication/4355188_On_the_second_eigenvalue_of_random_regular_graphs


texts: What to do with empty set during NFA to DFA conversion?

texts:
I am currently converting this NFA to a DFA

I have come up with the following DFA:

        0      1
->A    {A}    {B}
  B    {CA}
*CA    {A}    {AB}
 AB    {CA}   {B}

Although, I have no idea what to put for B. In the NFA, upon the B receiving 1 input, it goes nowhere - assumable unaccepted by the NFA. Do I send the DFA to a new, dead state upon receiving input 1 whilst in B?

I can try it:

        0      1
->A    {A}    {B}
  B    {CA}   {}
*CA    {A}    {AB}
 AB    {CA}   {B}
 {}    {}     {}

But is this correct by the rules of DFA?


texts: Algorithm to find maximum number of items that can be removed from buckets with set of condition

texts:
I am looking for algorithm to rather complex problem and I am wondering if this is some well known problem or can be translated to one.

Let's say that i have buckets B1, B2, B3 that contain some number of colored balls (red and green) and set of conditions K1=(1 green, 2 red), K2=(2 green, 1 red), K3=(2 green, 1 red) and NK1=1, NK2=1, NK3=3. This conditions says that K1 is a set of 1 green and 2 red balls and that we need 1 such set (NK1=1) and that set need to be in one bucket (we cannot get balls for K1 from different buckets, but if NK1=2 for e.g then we can get one set from one bucket and another from another bucket) etc. Now for e.g. we have in bucket B1 1 green and 2 red balls, in B2 2 green and 2 red and in bucket B3 2 green and 1 red. The question is what is the maximum number of balls of each color that we can pull out of the each bucket so that given conditions are still met. In this example we cannot pull out any green balls and we can pull out one red ball from bucket B2. Then 1 K1 is in B1, 1 K2 is in B2 or B3 and 1 K3 is in B2 or B3 but in other bucket than K2.

In reality I need to solve this problem for arbitrary number of buckets with balls in arbitrary number of colors and arbitrary numbers of conditions (conditions will contain small number of colors but there will be large number of different colors in total) and in SQL (but SQL part is not that important for now).


texts:
A furniture store is having a sale: purchase two items at the price of the more expensive one. John, having just moved to a new house, rushed into the store and chose $2k$ items of furniture, $f_1, f_2, \dots, f_{2k}$. The items are priced $p_1, p_2, \dots, p_{2k}$, respectively. Help John arrange the items in pairs so that the overall cost of the $2k$ items is minimal. Suggest an algorithm that runs in time $O(k\log k)$ and prove its correctness and running time.

Ok, so it sounds not too complicated: first, I will sort all the $2k$ items by their prices to array, and then each cell and his next are one couple. This takes time $O(k\log k)$.

How can I prove the correctness of what I suggest? I thought about assuming that there is a cheaper solution to get a contradiction but I dont know how to prove this.


texts: What are the first computer science papers that used asymptotic time complexity?

texts:
When was big O first used in computer science and when did it become standard? The Wikipedia page on this cites Knuth, Big Omicron and Big Omega And Big Theta, SIGACT April-June 1976, but the beginning of that paper reads

  Most of us have gotten accustomed to the idea of using the notation
  $O(f(n))$ to stand for any function whose magnitude is upper-bounded by a
  constant times $f(n)$, for all large $n$.

This quote indicates that the idea and notation were already in common use.

The Wikipedia page also cites math papers from the late 1800s and early 1900s, but that doesn't quite answer the question. In particular, I've heard researchers who were around back then (in the 60s and 70s, not the late 1800s) say that when asymptotic analysis was first used, some people pushed back, saying that wall clock time was a better metric. However, no one I've talked to can cite the specific papers that got pushback like this and I'd like to find evidence that can confirm or deny these stories.


texts: Why do we prefer DFS to find connected components?

texts: In finding the connected components in a graph, why do we use DFS, instead of BFS?


texts:
I am working on the following problem:

Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex
is connected to every other vertex. Recall also that a clique is a complete subset of some graph.
The graph coloring problem consists of assigning a color to each of the vertices of a graph such
that adjacent vertices have different colors and the total number of colors used is minimized. We
define the chromatic number of a graph G to be this minimum number of colors required to color
graph G. Prove that the chromatic number of a graph G is no less than the size of a maximal
clique of G.

So far, I have been thinking about the problem and came up with the following:

In a clique, every vertex is adjacent to every other vertex
Therefore, since the problem states adjacent verteces always have different colors, the number of colors needed would be the number of verteces in the clique
Thus, the chromatic number of any graph G has to be at least the maximal size of the clique, per the definition of a clique.

Can someone verify if my understanding is correct? Or am I glaringly not understanding a clique?


texts: Language Features Not Translatable into Lambda Calculus

texts:
Haskell is said to be a pure language because the language features are directly translatable into lambda calculus.

My question is: for languages considered to be non-pure functional languages (e.g. Scala, OCaml), which aspects of those languages are not translatable into lambda calculus?


texts: Figure out recursive function for this problem

texts:
I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function.

There is N students (N is even) in class. The class will be divided into two groups with the same number of students. Each student has it's own preference what group he want's to be a part. Group 1 and Group 2.

I have to create a DP algorithm which computes the best division of the class so the maximum possible students will be satisfied.

What I have done so far:

S|G
1|A
2|B
3|B
4|B
5|A
6|B

I rewrited the table above to this:

S|A|B
1|1|0
2|0|1
3|0|1
4|0|1
5|1|0
6|0|1

There is $1$ when student want's to be a part of the group. So we are looking for the maximal sum of 0s and 1s under condition that both groups has to have the same number of students.

But when I try to create a recursive function I can't figure out even what parameters should be there.

$OPT() = max(OPT(),OPT())$

Could you give me some hint?

I think that it could be solved another way - let's take a group A. We can consider the table as an array, where values are 0s and 1s. If a student want's to be in group A, there is 1, otherwise, there is 0. So we can sort the array and divide it into two parts. But it's not a DP approach.


texts: Is $2^n$ steps enough to tell if DTM will run forever?

texts:
In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after $2^{|f(x)|}$ steps on the machine $M$, reportedly to avoid infinite running time.

My question is: how is it that $2^{|f(x)|}$ steps is enough to tell if machine $M$ will run forever or not?


texts: Can partial sorting help with lookup cost in arrays?

texts:
Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(\log(n))$. That means it is sometimes worthwhile to sort an array. However, that is a trade-off as a sorting algorithm has a time complexity of $O(n\log(n))$.

As far as I know, you can not sort an array in less than $O(n\log(n))$  time. I am however wondering if there is any algorithm that can partially sort the array in less time than that? I am pretty sure you can not look up a value in such a partially sorted array in $O(\log(n))$ time, but can you do better than $O(n)$?

In short, is it possible to process an unsorted array with an algorithm faster than $O(n\log(n))$ such that a lookup algorithm can do a search faster than $O(n)$, though not as fast as $O(\log(n))$?


texts: Why is IDA$^*$ faster than A$^*$? Why does IDA$^*$ visit more nodes than A$^*$?

texts:
I used IDA$^*$ for optimally solving the 8-puzzle and my friends used A$^*$ for it too (with same manhattan distance heuristic).

I calculated the average running time and number of nodes of my algorithm for 20 examples and my friend's algorithm. The time average for my algorithm was much faster than my friend's algorithm, but my average number of nodes visited is a lot more than my friend's.

I know IDA$^*$ visits each node more than once but why is it faster than A$^*$?


texts: Order preserving encoding of strings to numbers

texts:
I want to encode strings as real numbers while preserving order. The order of the strings is the lexicographic order (as used in phone books); the order of the numbers is the standard order.

Is there an general (i.e. no additional conditions such as e.g. known max string size) encoding with this property?


texts:
I'm not sure if this is the right site to ask, but I couldn't find a another one.

Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For example: (pseudocode)

int get() & void set(x) {
    return x to get
}

void main() {
    set(1)
  & set(2)
  & print(get())
}

would randomly output 1 or 2.

Yesterday I learned about hypergraph rewriting as a programming model. LMNtal for example.

My question is whether every join can be expressed as a hypergraph. The pseudocode from above would for example transform into:


texts:
Given a 2HornSAT problem. Its possible in linear time to find the minimum solution to the problem i.e. that has minimum number of variables set to 1 in the solution.

Now let us consider another variant of the problem:

Given a positive integer K, is there a solution to the 2HornSAT such that exactly K variables are set to 1?

Is this problem NP-Complete. I am struggling with its reduction but it seems this might be difficult.


texts: Explanation of implication-introduction rule

texts:
I read in Proofs and Types by Girard et alii. the following excerpt that talks about the calculus of natural deduction:

  Now a sentence at a leaf (of the deduction tree) can be dead, when it
  no longer plays an active part in the proof. Dead sentences are
  obtained by killing live ones. The typical example is the
  $\implies$-introduction rule:

  $$ \dfrac{\stackrel{[A]}{\stackrel{\vdots}{B}}}{A \implies B} $$

  It must be understood thus: starting from a deduction of B, in which
  we choose a certain number of occurrences of $A$ as hypotheses (the
  number is arbitrary: 0,1,250,$\ldots$), we form a new deduction of
  which the conclusion is $A \implies B$, but in which all these
  occurrences of $A$ have been dicharged, ie. killed. There may be other
  occurrences of $A$ which we have chosen not to discharge.

  This rule illustrates very well the illusion of the tree-like
  notation: it is of critical importance to know when a hypothesis was
  discharged, and so it is essential to record this. But if we do this
  in the exmaple above, this means we have to link the crossed A with
  the line of the $\implies$I rule; but it is no longer a genuine tree
  we are considering.

May I ask you for an explanation and example of this situation?


texts: Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution)

texts:
Presume I have the following case:

int value a
int value b, for which a < b
int value i, for which a <= i < b
I need an int value x, for which a <= x < b, randomly chosen, according to a non-uniform distribution: the distribution should follow a bell curve which is centered around i.

In Java, I have the following methods available on java.util.Random:

nextInt(int m): int between 0 and m
nextDouble(): double between 0.0 and 1.0
nextGaussian(): double between -Infinity and +Infinity, usually close to 0.0.

How do I build such a non-uniform distribution from these building blocks? How do I reliably and efficiently transform nextGaussian() into nextGaussian(a, b, i)? The part I am struggling with is to enforce that x is selected between a and b (without doing a trial-and-error).


texts: Question about big O notation for function

texts:
I'm just starting to learn Big O Notation and I was trying to understand how this function would scale:

$\frac{n(n-3)}{4}$

If the function was $n^2$, it would be quadratic, so O(n^2). However, the denominator gives me pause. Is this still a O(n^2) function? This is not homework. Thanks in advance for the help and clarification.


texts: What Exactly is "Improvement" in Seed AI?

texts:
From LessWrongWiki, a seed AI

  [I]mproves itself by recursively rewriting its own source code without human intervention.

Some would even say this could bring about an Intelligence Explosion. Many of these sources mention that it recursively "improves" itself. What exactly does that mean? How do you define "improve"?

Many people say that since it "improves" itself recursively, the jumps in intelligence would be ever-increasing. However, they also mention that an AI like this would have a goal; for example maximizing knowledge or maximizing human happiness. How would this translate into maximizing of the ability to maximize? You could also maximize for speed, let's say. How do you measure speed? A test, like the TSP? But then wouldn't the machine optimize specifically for solving the TSP, and nothing else? How would that translate into an increasing ability to optimize itself?

In other words, what would one maximize for in an implementation of Seed AI?


texts:
I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element?

According to https://en.wikipedia.org/wiki/Quadratic_probing:

  In the case of quadratic probing, with the exception of the triangular
  number case for a power-of-two-sized hash table[2], there is no
  guarantee of finding an empty cell once the table gets more than half
  full, or even before the table gets half full if the table size is not
  prime.

Does this mean that Load Factor should always be 0.5 for a Hash Table that uses Quadratic Probing?

What is the proof of this claim?


texts: What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?


texts: Approaches to the size constrained weighted set cover problem

texts:
I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$.
Assuming this is a pretty straight-forward variation of weighted set cover I ended up quite confused with only one, also rather recent paper by Golab et al. [1].

Am I missing something here?

[1] Golab, Korn, Li, Saha and Srivastava, Size-constrained weighted set cover. In _Proceedings of 31st International Conference on Data Engineering (ICDE), pp. 879–890. IEEE, 2015. IEEE Digital Library; author PDF.


texts: Why is a Tree a concrete data structure and not abstract?

texts:
It seems to me that a tree or a heap is a concept and not a concrete implementation of some other abstract data structure.

For example a heap can be implemented with a table. Then why it is not considered abstract?


texts: Training a model to match two time series

texts:
Context

I have two related time series, I want to learn to produce one from the other. However, they aren't synchronous, and the lag between the two does not revert to the mean, it accumulates.

Known relationship, dynamic programming

I am given two, random, ergodic, time series $X = (x_1, \ldots, x_t, \ldots, x_N)$ and $Y = (y_1, \ldots, y_t, \ldots, y_N)$

Given two time series, a classic dynamic programming problem consists in minimizing an edit distance between the two. For instance, we can assign a cost $c(X,X') = \frac{1}{2}\lambda(|X|-|X'|)$ to removing some elements in $X$, forming $X'$, and likewise a cost $c(Y,Y') = \frac{1}{2}\lambda(|Y|-|Y'|)$ to removing elements from $Y$, forming $Y'$. We impose $|X'| = |Y'| = N - P$.

We then minimize $\lambda P + \frac{1}{2}||X'-Y'||_2^2$

Once again, so far this is vanilla dynamic programming.

Unknown relationship

Suppose however that we want to minimize

$$\min_{\theta} \left(\lambda P + \sum_{t=1}^{N-P} (y'_t - f_{\theta}(x'_t))^2\right)$$

where $f_{\theta}$ is a parametric function (think neural-net or Gaussian process)

This is a trickier situation because we do not know in advance what the cost
function is going to be.

First idea: iterative optimization

My first idea is to iteratively optimize for $\theta$ and then solve the dynamic programming problem. However, unless I start with a good idea of $\theta$, this is unlikely to converge.

Consider indeed the following example $X=(451,5,3,1,7,9,\ldots,N)$, $Y=(25,9,1,49,81,\ldots,N^2,-238)$.

A very good fit is to drop the first element of $X$ and the last element of $Y$ and just let $f(x) = x^2$. However, unless I first discover this relationship, I am unlikely to ever come up with removing the first element of $X$ and the last element of $Y$. I need a good initialization of $X'$ and $Y'$.

Second idea: initialization with K-mean

My second idea is to use K-means to initialize $X'$ and $Y'$. The idea would be as follow.

Perform K-means clustering on the values taken by X, and K-means clustering on Y
Minimize
$$\min_{\sigma \in S(K)} \lambda P + \sum_{t=1}^{N-P} \delta(k_y(y'_t),\sigma(k_x(x'_t)))$$
where $\sigma$ is taken over the set of permutations of $K$ elements, $k$ represents the cluster number of an element.

The hope here is that enough datapoints will be correctly matched between $X$ and $Y$ and I can then iteratively learn $\theta$.

The question

My question is two-fold:

Is there a nicer approach with stronger theoretical guarantees?
Are there parametric functions which are somewhat generic enough for this to be solvable exactly or for convergence to be guaranteed? For instance, if $f$ is a linear transform, is there an exact solution?


texts: Interpreting a proof of $2^\mathbb{N}$ being uncountable

texts:
Suppose I have the following proof:
open import Agda.Builtin.Equality
open import Data.Nat.Base

data ⊥ : Set where

data  : Set where
  I :
  O :

inv :  →
inv I = O
inv O = I

invNeq : ∀ d → d ≡ inv d → ⊥
invNeq I ()
invNeq O ()

data Idx : Set where
  at : ℕ → Idx

ℝ : Set
ℝ = Idx →

_≈_ : {a b : Set} → (f₁ f₂ : a → b) → Set
_≈_ f₁ f₂ = ∀ x → f₁ x ≡ f₂ x

diagEx : (f : ℕ → ℝ) → ℝ
diagEx f (at n) = inv (f n (at n))

doesn'tBelong : (f : ℕ → ℝ) → (n : ℕ) → (f n ≈ diagEx f) → ⊥
doesn'tBelong f n funEq = invNeq (f n (at n)) (funEq (at n))

We encode real numbers as functions from natural numbers to binary digits, then (in diagEx), given some mapping f from natural numbers to reals (or, rather, some subset of those), we build a function that doesn't belong to said mapping, and then prove (in doesn'tBelong) that, for any mapping f, there exists a function (built by diagEx f) that isn't equal to any real number enumerated by the f. This, of course, includes f's claiming to be surjective, so that's largely the diagonal argument for proving uncountability of reals. Yay!
Or at least that's the intent of the proof. But what have we really proven? Could it be that we've only proven that there doesn't exist a terminating numbering of reals? Or a computable one?
My concern is that we're working in some language, and said language only allows terminating functions (modulo some irrelevant details, but even with them it's about computable functions). On the other hand, we don't rely on the computational behaviour of f at all, so, in theory, this f could be postulated (or, stretching it a little, it could even go ahead and consult some external oracle about each next digit without making the system inconsistent, I guess).
So what's the power of this proof? What's the right tool to reason about this kind of questions? It feels related to model theory, but I have very passing familiarity with that subject.


texts:
Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree.

The problem though is that after reading everything I think I could read from Wikipedia to blog articles and even Stack Exchange answers I couldn't wrap my head on how this is implemented. Maybe it's simpler than I think but I'm looking at it from the wrong perspective, no idea.

So let's take this HTTP request:

GET /hello HTTP/1.1
Host: www.stackoverflow.com
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Accept: */*

With a Trie are you going to iterate on GET, then "/" then "hello" then "HTTP" then "1.1" etc until you get to the end of the request with matches or does it work differently than this?

               root
           /  /   \  \
         GET POST PUT DELETE
         /
       "/"
       ...
       /
    "HTTP"
      /
     "1"
     /  \
   "0" "1"

I have a hunch that that's not exactly the case because it has the potential to lock a loop or function where it's executed in, or waste resources if event'ed. Given the fact that this solution is considered when the HTTP routing itself becomes a problem it must work differently?


texts: Understanding this answer: A CFG defines a language as a the smallest solution to a system of language equations

texts:
Statement comes from this answer. A blanket statement that this is a well-known fact is made in this other question.

I have never heard of a language equation. But I am just a student. Given the syntax, is this equating the derivations of a CFG grammar to equations?

In other words, is this bit from the answer $A=ABa$ meant to be considered equivalent to a BNF derivation $A \rightarrow ABa$? (where $A$ and $B$ mean the same as in the original answer -- variables that decompose to terminals containing $a$)

Or is there some other meaning being expressed here? From the second question that I found after I typed this question it seems to mean something different. Can someone "ELIStudent"?


texts: Algorithm to solve Turing's "Halting problem"

texts:
"Alan Turing proved in 1936 that a general algorithm to solve the
  halting problem for all possible program-input pairs cannot exist"

Can I find a general algorithm to solve the halting problem for some possible program input pairs?

Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?


texts: Showing the following sequents are not valid

texts:
$\lnot \forall x P(x) \models \forall x \lnot P(x)$
$P(x) : x$ is divisible by 2
or $P(x) : x$ is a dog.
or $P(x) can be anything.

I want to show the following sequents are not valid ..Isn't the following sequents equal or the first sequent the whole negation of the statement and the second sequent is the negation of the $P(x)$ .. Can anybody explain this with examples?


texts: Number of words in the regular language $(00)^*$

texts:
According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation

$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$.

The language $L =\{ 0^{2n} \mid n \in\mathbb{N} \}$ is regular ($(00)^*$ matches it). $s_L(n) = 1$ iff n is even, and $s_L(n) = 0$ otherwise.

However, I can not find the $\lambda_i$ and $p_i$ (that have to exist by the above). As $s_L(n)$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of summands like in a Taylor expansion. Can anyone enlighten me?


texts:
I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit vector.
But I could not understand how to build it?  Because it requires a degree of your nodes in advance. Or you have a Trie tree build already. So using level order traversing we can make a LOUDS representation of the Trie tree.
Can anyone help me in understanding?
Note: I am trying to make a space-efficient data structure for top k completion.


texts: what does the redundancy of a code means?

texts:
I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits.

But what does that means? I was trying to get that from the proof of that fact but what they proved instead was that

there exists a such (with the structure they propose) code whose redundancy is at most $\log(6n-3)$ bits

and in the proof itself they just said that the cardinality of the code is greater or equal than $\frac{2^n}{6n-3}$.

How does that proved the hypothesis?

Also, if I have my own code how do I compute the redundancy (or a reasonable bound on it?)


texts:
Binary tree with external leaves is a 5-balanced tree if the path from the root to the farthest external leaf is no more than 5 times as long as the path from the root to the nearest external leaf, and if his right and left subtrees are 5-balanced too. Show that the height of such a tree is O(logn).

I was trying to prove it by finding the minimum number of nodes in such a tree with height h and then saying that the height of the tree is at most the log of this number, but I'm not sure how to find it.
Thanks


texts:
Is my searching about the types correct?
Types of recordings on magnetic disks
Write: The current which goes through the coil produces magnetic field and then the pulses are sent to the head which produce magnetic pattern recorded on the surface.
Read: There are 2 ways (Traditional: In this method the magnetic field move relative to coil produces current and coil is the same for read and write.)
(Contemporary: Separate read head, close to write head, partially shielded magneto resistive (MR) sensor, electrical resistance depends on direction of magnetic field, High frequency operation, Higher storage density and speed)


texts: Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$

texts:
This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ blocks. I call a bunch of nodes a block, the blocks are of size $k$.

My goal is to store a perfectly balanced binary search tree with $n$ nodes as an array and be able to traverse any root to leaf path in a small number of steps. To achieve this I want to read blocks of $k$ elements and upon seeing those $k$ elements I should be able to decide where in the array I need to read the next $k$ elements from. I want to repeatedly read $k$ elements and traverse from root to leaf node in such a way that everytime I read $k$ elements I know where to move next inside of the array. A larger $k$ would mean more "branches" and a smaller number of steps. This sounds like a B-tree to me.

I want to store a perfectly balanced binary search tree as an array but in such a way that I can traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ blocks.

Such an approach minimizes the number of blocks read and can be used to minimize memory accesses which is my final goal.

Does anyone have any resources where I could learn more about or how could I approach this?


texts: Is it possible to constract Moore or Mealy machine with a different size of input and output?

texts:
Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size.

I want to construct FSMs to produce different transformation patters:

copy 2 times: 11 -> 11011, 101 -> 1010101
trim: 011100 -> 111, 000110 -> 11
fill zeros by 1 between 1: 01000100 -> 01111100, 01010 -> 01110

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine) or should I switch to context free languages?


texts: String version of even-odd partition problem

texts:
Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version.

String even-odd partition

INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e.,  $n$ pairs of strings over $\{0,1\}^*$

QUESTION: Does there exist $(b_1,\dots,b_n) \in \{0,1\}^n$ such that $x_{1,b_1} \cdots x_{n,b_n} = x_{1,1-b_1} \cdots x_{n,1-b_n}$?

Equivalently: for each pair, we can either swap the two strings or leave them alone; then we want to know if the concatenation of the left part of each pair can equal the concatenation of the right part of each pair.

Or, in other words, we are trying to partition every pair into two strings to obtain concatenated strings $W_{even} $ and $W_{odd}$  such that $W_{even}= W_{odd}$, where exactly one string from each pair goes to $W_{even}$  and the other goes to $W_{odd}$.  The selected strings have to stay in the same order they appear in the input.

It feels like this should be NP-complete by a reduction from even-partition problem but I can't find an explicit reduction; I am having difficulty in representing integers by appropriate strings.

Is there a simple reduction to prove the NP-completeness of this string variant?


texts: Is it true that NEXP = EXP when the input binary strings have size O(n)?

texts: I have a question about this. Because if the input binary strings have size of O(n), it takes exponential time to list all possibilities of it. If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one, which is still in exponential time in total. It seems like NEXP=EXP under this circumstance.


texts: Using two hash functions for increased password security?

texts: Forgive me for my brief knowledge on hash functions as I am not from a computer science background, however I am researching password security for my thesis and have been looking into hashing functions for password security. I understand that a password goes through a hashing function and is stored in a separate database, at which point if the user enters the same password at a later date, that entry is then ran through the same hashing function and checked the output is the same. My question is, if lots of companies are being breached and passwords have been found out using the algorithms, would it be more secure to then use a second hashing function on the already hashed password and store all the password entries 'double hashed'?


texts: Exploration in reinforcement learning when state space is huge

texts: When the state-action space is huge I know I can use function approximators to generalize but how can I explore? Doing an exhaustive search seems very naive. What DeepMind for example did to explore the state-action space in Atari games?


texts: Solve Hamilton Circuit with Hamilton Path

texts:
I want to show the reduction $HC \leq HP$.
Let $G=(V,E)$ be my undirected graph.

My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true for all edges, we have a Hamiltonian circuit in $G$.

It is pretty trivial to proof the first direction (when we have a Hamiltonian circuit in $G$, we will always have a Hamiltonian path in $(V,E\backslash\{e\})$ - independent from the edge we choose).

I really have trouble finding a formal proof for the other direction (either

$\forall e\in E$ Hamiltonian path exists in $(V,E\backslash\{e\})$  $\Rightarrow$ Hamiltonian circle exists in $G$ or
There is no Hamiltonian circle in $E$ $\Rightarrow$ $\exists e \in E:$ $(V,E\backslash\{e\})$ has no Hamiltonian path


texts: Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

texts:
Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$.

Now let $T'$ be some other spanning tree of $G$ (doesn't have to be minimum) with edge weights: $w'_1 \le w'_2 \le ... \le w'_{n-1}$.

I need to prove\disprove the following claim: for every $i$:  $w_i \le w'_i$.

I've tried to find a counterexample, but I wasn't successful. So I'm quite sure the claim is correct. However, I had trouble to prove it formally.

I assume the contrary, which means there is an $i$ that satisfies $w'_i < w_i$ and I take the first one that does. I tried adding it to the tree $T$ or trying to find a minimum spanning tree with this edge using Kruskal, but no luck.


texts: Devising a way to spot a contradiction given a set of statements using graphs

texts:
If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John.

Would there be a way to figure out that there is a contradiction in this set of statements using graphs?

My attempt at it was to symbolize each of the names, assuming they have different first letters to statements like, J = M, M = S, C = S, C ≠ J.

My idea is to find a cycle after using DFS on some graph but I'm having trouble making the actual graph which is perhaps the most troublesome part.

I hope I'm on the right track. Any help would be much appreciated!

Edit: The comment makes a good point and the statements do have inequalities as well, but I'd like to make another attempt at that on my own afterwards. If the question were to be simplified to just "as tall" and "not as tall", what sort of graph would I make?


texts: If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular

texts:
I'm having trouble being 100% sure about this answer. I feel like it's false but I'm having trouble coming up with a complete answer. Can someone explain this step by step?

Thanks.


texts: What is the name for the complexity class $O(n^{1+\epsilon})$

texts:
Sometimes problems can be solved in $O(n^c)$ time for any $c > 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive constant. I want to know the terminology for describing this complexity class.

For example, I would call a $\Theta(n)$ algorithm "linear". I would call a $\Theta(n^2)$ algorithms "quadratic". I would call a $\Theta(n \cdot log^c(n))$ algorithm "nearly linear". (Note that nearly linear is better than $O(n^{1+\epsilon})$.)

What do I call algorithms that are in $O(n^{1+\epsilon})$?


texts: Is there a metric or distance of two languages?

texts:
Given a language $L$, I am finding a method to evaluate the advantage of an automaton to decide $L$.

My goal is to decide a language $L$ (and maybe it is not decidable for automata). If one constructs an automaton $A_{1}$ whose laguage is $L_{1}$, I want to know the advantage of $A_{1}$ for decisidng $L$. If there is a distance or metric of two languages $d(\cdot, \cdot)$, I can define $\mathrm{Adv}_{L}(A_{1}) = d(L_{1}, L)$. Thus, we can say $A_{1}$ is better than $A_{2}$ respect of $L$ if $\mathrm{Adv}_{L}(A_{1}) > \mathrm{Adv}_{L}(A_{2})$.

In my opinion, the follow conditions are satisfied at least.

1 It is non-negativity and identity of indiscernibles, $d(L_{1}, L_{2}) \geq 0 ~\text{iff}~L_{1} = L_{2}$.

2 It is symmetry, $d(L_{1}, L_{2}) = d(L_{2}, L_{1})$.

3 If $L_{1} \cap L \subseteq L_{2} \cap L$ and $L_{1} \setminus L = L_{2} \setminus L$, then $d(L,L_{1}) \leq d(L,L_{2})$.

4 If $L_{1} \cap L = L_{2} \cap L$ and $L_{1} \setminus L \subseteq L_{2} \setminus L$, then $d(L,L_{1}) \geq d(L,L_{2})$.

Note that I am not sure the condition 3 and condition 4 above is suitful.

Follows may be helpful.

How similar are two DFAs? -not just binary equivalence-

Measures and probability in formal language theory


texts: Computing the closest match of an automaton and a string

texts:
I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting for the automaton). I've looked around and found Levenshtein Automaton but had trouble finding out how it would be implemented from my automaton.

Also, are there any other methods that would be suitable/worth looking at for my problem?


texts: Can anyone help me understand the matches to this regular expression?

texts:
My professor gave us this pattern "/[aeiou]+[1234567890]*[a-z]?/" and I'm trying to find matches in "ae12abc r2d2 a1steaksauce".

The resulting matches the professor gave us are ae12a, a1s, eak, auc, and e.

I think I'm totally misunderstanding how this is supposed to work. Why are ae12abc, r2d, or a1steaksauce not possible matches? Thanks in advance, I really appreciate any help with this!


texts: Find the longest contigous subsequence where each pair's difference is at most p

texts:
Given input sequence $x_1,...,x_n$, find the longest contigous subsequence $x_i,... x_l$ where each pair $(x_j,x_k)$ satisfies that $|x_j - x_k| \le p$.

I have come up with simple $\mathcal{O}(n^2)$ solution.

I'm sure there is a better way so I'm looking for $\mathcal{O}(n)$ or at least $\mathcal{O(n \log n)}$ solution. Thanks for any help!


texts:
I'm trying to decode the following Hamming sequence (using EVEN parity and knowing there is a 1-bit error), which contains an ASCII value: 01100110101

I've tried to check for the correctness of each parity bit:

    p1 p2 d3 p4 d5 d6 d7 p8 d9 d10 d11
     0  1  1  0  0  1  1  0  1   0   1
p1 - 0     1     0     1     1       1
p2 -    1  1        1  1         0   1
p4 -          0  0  1  1
p8 -                      0  1   0   1

p1, p4 and p8 checks are all even and correct.

p2 check is odd, hence the parity bit is incorrect and needs to be flipped. The actual message then becomes 00100110101 and the ASCII value can be read as 1011101.

Supposedly this value is incorrect - can anyone point out the mistake I made?


texts:
I was reading about deadlocks in Operating Systems. Where I came across two examples below.

Circles with label $P_x$ are processes. Squares with label $R_x$ are resources.  Each dot in the square represents single instance of resource type $R_x$. An edge from $R_x$ to $P_x$ means an instance of resource $R_x$ is allocated to process $P_x$. An edge from $P_x$ to $R_x$ means the process $P_x$ is waiting for getting an instance of resource $R_x$ allocated.
Now consider below two resource allocation graphs

The example on left involves deadlock while the one on the right did not involved deadlock.

I can understand that in right-side figure, if $P_2$ releases its instance of $R_1$, it can be assigned to $P_1$, breaking the circular wait. Or if $P_4$ release its instance of $R_2$, it can be assigned to $P_3$, breaking the circular wait. However we cannot break circular wait in left-side figure.
While I can try out this on any given resource allocation graph and decide if there is deadlock or not, I want to know can we have a generalized rule for this which can tell what exactly it is which is contributing to the deadlock, especially in case of multiple instances of resources are there. I did not found any reference / book speaking of this clearly. So after a bit of thinking I came up with following fact:

If there are multiple instances of same resource, for deadlock to exist, for any combination of two processes, if both are allocated an instance of same resource, then both should be a part of at least one cycle.

In right-side figure above, there is no deadlock because

processes $P_2$ and $P_3$ are allocated instances of $R_1$, but they both are not part of any cycle
similarly processes $P_1$ and $P_4$ are allocated instances of $R_2$, but they both are not part of any cycle

In left-side figure above, there is a deadlock because

processes $P_1$ and $P_2$ are allocated instances of resource $R_3$ and are part of same cycle,$P_1-R_1-P_2-R_3-P_3-R_3-P_1$

So am I correct with the above realization of fact? Or there are more aspects/conditions to the above fact (of when deadlock is present and when not) that I am missing?
What I am asking is if there is any other condition which if met, instead of the above one, will still result in the deadlock (in the context of multiple instances of resources and apart from four classic conditions of deadlock: mutual exclusion, no preemption, hold and wait and circular wait)?


texts:
How can i show/explain/prove that Max-Cut is in NP?
"For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem."

Thanks!


texts: Why is the sequence "3,3,4,5,2" considered a bitonic sequence?

texts:
Why do we consider the sequence "3,3,4,5,2" a bitonic sequence?

In the sequence, "3,3,4,5,2", the sequence is

constant for "3,3",
increasing for "4,5", and
decreasing for "5,2".


texts: How to prove $\{ a^ma^lcb^{m+l}\mid m,l \in N \}$ is not regular using the Pumping Lemma?

texts:
I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.

Task:
Prove that $M = \left\{ a^ma^lcb^{m+l}\mid m,l \in N \right\} $ with $\sum =\left\{ a,b,c \right\}$ is not a regular language using the Pumping Lemma.

Here is my try:
First of all I would like to write  $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in  N \right\} $. Is this possible?

Proof:
Let $n\in N$ be fixed. Choose the word $w = { a }^{ 2n }c{ b }^{ 2n }\in M$ with $|w|\ge n$. Let $w=xyz$ be a decomposition with $y\neq \lambda $ and $|xy|\le n$. Then we have $x={ a }^{ 2i }$, $y={ a }^{ 2j }$ and $z={ a }^{ 2n-2i-2j }c{ b }^{ 2n }$ for $j\neq 0$ and $2(i+j)\le 2n$.

We choose $k=0$. Then we have $x{ y }^{ 0 }z = {  a }^{ 2n-2i }c{ b }^{ 2n }$. $\Longrightarrow x{ y }^{ 0 }z\notin M$ because $2n-2i\neq 2n$ for $j\neq 0$.
$\Longrightarrow$ M is not a regular language.


texts: Number of Times to Run an Evolutionary (Genetic) Algorithm

texts:
Evolutionary algorithms like genetic algorithms (GAs) are typically run multiple times and the outputted results are averaged across successive runs.

However, in the case of long-runtime algorithms (e.g., due to large population sizes or algorithm complexity), is there any justification for running GAs (and the like) only once? Clearly, statistical evaluation of variability is not possible in such a case.

I've not been able to find anything in the literature on the subject, so am asking here to gain some insight from the CS community.


texts: Algorithm for summation with lowest maximum temporary sum

texts:
I've got this problem on my last exam, which I struggle to deal with.

Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those numbers, but we can only use operation of summing two adjacent numbers. Goal of algorithm is to sum this sequence, so maximum of absolute values fromm sum from this operation will be lowest possible.
For example:
Let's say we have array -2 5 -3.
First we sum 5 and -3, so the temporary sum is 2, and our sequence changes to -2 2. Then we sum -2 and 2, so now our temporary sum is 0. As we see, maximum of temporary sums was 2, and we can't get any lower. (summing -2 and 5 would give us 3, which is higher that 2).

My goal on that exam was to find best complexity algorithm, and prove its correctness.
What I tried:
First thought was to use greedy algorithm, so just sum those two numbers which give lowest temporary sum right now.
Problem is, I can neither prove it is valid way to solve it, nor find any counterexample.


texts: Boolean circuit with two inputs and advice input is hard-wired

texts:
Claim : $\cup_{c,d} $ DTIME$(n^c)/n^d \subseteq$ $P_{poly}$

Proof : if $L$ is decidable by a polynomial-time Turing machine $M$ with access to advice family $\{\alpha_n\}_{n\in \mathbb{N}}$ of size $a(n)$, then we can use the cook-levin construction for every $n$ a polynomial-sized circuit $D_n$ such that on every $x \in \{0,1\}^n$, $\alpha_n \in \{0,1\}^{a(n)}$, $D_n(x,\alpha) = M(x,\alpha)$. That is, $C_n$ is equal to the circuit $D_n$ with the string $\alpha_n$ "hard-wired" as its second input.

Question : I am not getting the part that circuit is going to have two inputs one hard-wired as second input. How a circuit will like with two inputs. I have seen circuits with one input but not with two inputs (i.e. one input is hard-wired). I am thinking that it may be the case that they are attaching advice bit to each of AND and OR gate (increasing the fan-in). So I am not getting, how they are hard-wiring the advice string ?

Reference : http://theory.cs.princeton.edu/complexity/book.pdf


texts: Determine the optimal strategy and maximize the reward

texts:
Given an array of length n filled with objects which contain 2 ints (size and reward).

Now 2 players are taking turns, each player has an int value we call strength. Let's call them player A and player B, player A goes first.

Player A can pick whichever object from the array he wants and decrease the size of the object by his strength (pickedObj.size -= playerA.strength), he can also skip his turn by simply not picking an object.

Player B is simple minded and for all his turns uses the same greedy strategy: he picks the object with the smallest size and decreases it's size by his strength (pickedObj.size -= playerB.strength), player B can't skip turns.

Once a player decreases the size of an object to 0 (or bellow) he receives the reward (playerX.reward += finishedObj.reward) associated with that object. Each player starts with 0 reward points (playerX.reward = 0).

Given an array with n objects, player A with strength = m and player B with strength = k, compute the maximal amount of reward points that player A can win.

Examples:

Example 1:

obj[] array = `{ (9,5), (6,2), (7,3) }`;
playerA.strength = 4;
PlayerB.strength = 5;

int solution = determineMaxReward(array, 4, 5);

// The solution (max amount of money player A can win) is 10.

Explanation:

Round 1: Player A skips this round, player B picks arr[1] and therefore decreases it's size by his strength (now arr[1] = (1,2)).
Round 2: Player A picks and finishes arr[1] (playerA.reward += 2), player B picks arr[2] (arr[2] = (2,3))
Round 3: Player A picks and finishes arr[2] (playerA.reward += 3), player B picks arr[0] (arr[0] = (4,5))
Round 4: Player A picks and finishes arr[0] (playerA.reward += 5)

That's an optimal game for player A, the at the end he is left with 10 reward points which is the maximal amount of reward points he can possibly achieve.

Example 2:

obj[] array = `{ (2,1), (2,5) }`;
playerA.strength = 1;
PlayerB.strength = 2;

int solution = determineMaxReward(array, 1, 2);

// The solution (max amount of money player A can win) is 5.

Example 3:

obj[] array = `{ (9,3), (10,3), (4,1), (8,1), (9,2) }`;
playerA.strength = 5;
PlayerB.strength = 3;

int solution = determineMaxReward(array, 5, 3);

// The solution (max amount of money player A can win) is 10.

My current unproven (in the sense of optimality) approach:

For each object, I compute the minimal number of picks player A needs to make in order to finish that object. Then I reduce to the knapsack problem, size of the knapsack being the number of picks player A can do during the game, then the best way to fit the objects with their size and reward into the knapsack (such that the reward is maximized) is found.

Now I'm not sure if this is optimal, I can't find a counterexample where my approach doesn't work but I also can't prove that it's optimal. Any help/comments are appreciated.

This is a problem I have been struggling with for a while now, I encountered it during a programming contest in the context of dynamic programming.


texts:
I have various Boolean functions in the sum of products format. I "convert" these via combinatorial logic synthesis into a combinatorial network as an And-Inverter Graph - therefore this network only consists of 2-input, 1-output And-Gates and inverters. Every sum of products function is therefore "responsible" for a certain single output. The network is a multi-input and multi-output network, in- and outputs are Boolean (0 or 1). This network is also parsed as file, so it can be read from.

I know, that such a network can be proven to be correct, but I want to simulate this combinatorial network with certain inputs. My problem is, that I only find ways to simulate a sequential network - nothing for combinatorial networks. SAT-provers might be helpful, but because of the nature of this network and its functions, I already know the functions are satisfiable. I need to know, what output will be generated using certain inputs.

Is there any way to simulate and test a combinatorial network with certain inputs and save the outputs? I know there a SAT-provers out there, but I don't think I can really use those, as I need specific outputs and the Inputs have to be in a specific order. Logic Simulation might be the way to go, as the network is derived from Boolean functions, but I didn't find a way to simulate this network via anything.

Short Example: Network is some sort of adder, 4 inputs, 5 outputs. I then go through the inputs (0000, 0001, 0010, ...) and save the outputs of the network. I can't compare the outputs to a tables of "expected" outputs, because I don't know what the outputs will be (I only know them for certain test cases - the network probably won't be as easy as an adder).

Is there any way to simulate a network like this?


texts: Proof that L^2 is regular => L is regular

texts:
I'm trying to show $L^2 \in \mathsf{REG} \implies L \in  \mathsf{REG}$  with  $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right.
I first tryed to show $L \in \mathsf{REG} \implies L^2 \in  \mathsf{REG}$, by constructing an machine $M$ that consists of two machines $A=A'$ with $A$ recognizing $L$.
$M$ has the same start states as $A$ but the final states of $A$ are put together with the starting states of $A'$. Further $M$ uses the same accepting states as $A'$. Hope that makes sens so far :D
Now to show $L^2 \in \mathsf{REG} \implies L \in  \mathsf{REG}$ I'd argue the same way, but:
The machine $M'$ that accepts $L^2$ has to recognize $w_i \in L$ in some way, and because $L^2$ is regular, $M'$ has to be a NFA/DFA. So the machine has to check if $w_i \in L$ and this cant be done by using something else than a NFA/DFA.
This feels wrong and not very mathematical, so maybe somebody knows how to do this?


texts: Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.