texts: How to find greatest set intersection of at least a given cardinality?

texts:
While dealing with a problem, I uncovered this subproblem:

Input: A set of sets $S = \{S_1,...,S_r\}$ where $\mid$ $S_1$ $\cup$ ... $\cup$ $S_r$$\mid = n$, as well as a number $k<n$.

Output: A subset of $S$, $T = \{S_{t_{1}},...,S_{t_{p}}\}$ so that $\mid$ $S_{t_{1}}$ $\cap$ ... $\cap$ $S_{t_{p}}$$\mid$ $\geq k$ with $p=\mid T \mid$ maximized.

I.e. find the greatest number of sets in $S$ whose intersection preserves at least $k$ elements.

Is there any way of solving this problem in reasonable time, say polynomial in $r$ and $n$?

I tried to create an algorithm to solve the problem in reasonable time for large sets and $n$ and got nowhere. There's the obvious brute force algorithm that runs in $n2^r$ time. I also tried to construct a DP algorithm that used smaller subsets for optimal substructure, i.e. making use of $(A \cap B) \cap C = A \cap B \cap C$ and that if $\mid A \cap B \mid < k$, then it's not worth searching any further with $A\cap B$. However, I didn't get anywhere since the number of different subsets grows too quickly.

On the one hand, the problem feels kind of "set coverish" and thus I suspect it's hard. On the other, I'd imagine a problem this simple to be mentioned in some list of hard problems if it were intractable.


texts: Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?

texts:
Here is pseudocode for the algorithm:

select(L,k)
{
if (L has 10 or fewer elements)
{
    sort L
    return the element in the kth position
}

partition L into subsets S[i] of five elements each
    (there will be n/5 subsets total).

for (i = 1 to n/5) do
    x[i] = select(S[i],3)

M = select({x[i]}, n/10)

partition L into L1<M, L2=M, L3>M
if (k <= length(L1))
    return select(L1,k)
else if (k > length(L1)+length(L2))
    return select(L3,k-length(L1)-length(L2))
else return M
}

Here is some analysis of the algorithm: http://www.ics.uci.edu/~eppstein/161/960130.html

The analysis suggests to use the recurrence relation $T(n) \leq \frac{12n}{5} + T(\frac{n}5) + T(\frac{7n}{10})$.  Solving this we get linear work for a call.  But aren't there log many recursive calls?  So that would be $n\log n$.

Put another way, conceptually this algorithm seems like it could be described as "for each call, cut the search area kind of like binary search, but not guaranteed to cut the search area by as much as binary search, and add a linear time partition".  Binary search runs in $O(\log(n))$, so adding a linear search per call would make it $O(n\log(n))$.

What am I not understanding about the linked analysis?


texts: Does inserting and immediately removing a node change a red-black tree?

texts:
I have the following problem:

  Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it does not. Does deleting a leaf node from a red-black tree, then reinserting the same node always result in the original tree? Prove that it does or give a counter-example if it does not.

I have used several demos, but none of them have made much sense to answer this question. I havent been sure as to yes or no, I am still new to binary trees.


texts:
(Note: I couldn't put "balanced tree" in the tags ; this topic isn't about balanced search trees, just balanced trees.)

Let $A$ a binary tree.

We have the relation: $log(|A|+1) \leq h(A) \leq |A|-1$ where $|A|$ denotes the size of A (the number of nodes) and $h(A)$ its height.

Then I was told that A is balanced if $h(A) = O(log|A|)$. I don't really understand what that means. I know the symbol $O$ when we use it in maths with "$n$" stuff. For exemple $u_n = O(v_n)$ when $n \to +\infty$ or $f = O(g)$ at a certain point $x$. But there, how can we told that the tree $A$ "evolves"?

Applying the definition, it would mean that $\frac{|A|}{log|A|} \leq M$ but for a given tree, this is always true. So do we fix set the tree's size and have the relation for any size or do we fix the size and have the relation for any height, or something else?

Thanks.


texts: Understanding Logical to Physical Addressing

texts:
I am trying to understand the concept of logical to physical addressing.
I am given 72 physical addresses (0-71) with values

A virtual address = 2^(p+w)
p = page bits
w = word bits

I know the page table is of size 6 indexed 0-5

If a page size is 16 words does that mean that the offset(w)=4, giving me 2^(p+4).

If thats the case how do I determine what the page number (p) if given a logical address of 12?  I was thinking it would be 3 because I would need 3 bits to find the index of the page table 0-5, giving me 000 1100, index 0, offset 12. I feel like I might be missing something.


texts: Algorithm to generate a token as survey summary

texts:
I'm searching for an algorithm but struggle to find anything, as I'm not sure how to formulate it correctly. I created a simple survey app in Angular with 24 questions and each has 2-5 answers. When the user answered all the questions I'd like to give him a token (as short as possible) on the result page that he can note down, so the next time he can enter the token instead of having to answer all the questions again.
My thought process so far:

I can store the information in an array with 24 entries [1, 4, 2, ..., 2, 3]
As all values have 1 digit I can remove everything but the numbers 142...23

This still leaves me with a 24 digits long number. Nothing one would like to note down and type out by hand. So next I tried to convert this number (with ().toString(2)) to a binary with the goal to turned that binary into a human readable string with String.fromCharCode. But all I got was the rather not so human readable æ\u000f\u0000³KH\u0000\u0000\u0000 for my test input.
I could break down the number into digit pairs (e.g. 120422... -> [12, 04, 22, ...]) and map each of these to a character (00 -> A, 01 -> B, ...), but I think there must be something more elegant and efficient, as it would only half the original size. Although using 3 digits for mapping would result in 125 combinations which is rather hard to map to the alphabet, even with upper/lowercases and special characters. But I'd be very happy to hear your ideas. Many thanks in advance!


texts: Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?

texts:
Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of the variables in an equation, we can deduce the missing one.

  Does there exist a set of variables $R \subseteq V$ with $|R| \leq k$ such that revealing these variables allows us to deduce all variables?

Is this problem NP-complete? What if all equations have degree $\leq d$?

I'm ultimately interested in the search version of this problem (where we actually need to find minimal $R$).


texts:
If I have 2^32 bytes (512 MB) of physical memory, and we assume that each page is 2^10 bytes, how would I work out what the physical and logical address space would be?

No explanation that I can find makes sense to me.


texts: Is Timsort more efficient than merge sort and why?

texts: I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.


texts:
In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean that these kind of intersections will be simply ignored?

In other words, do the fast intersection algorithms require that the are no single-color intersections? Or they can work with such intersections but will find only bi-chromatic intersections?

The red-blue line segments intersection problem can be stated as: "Given a disjoint set of red line segments and a disjoint set of blue line segments in the plane, with a total of n segments, report all k intersections of red segments with blue segments." (From "A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections", Timothy M. Chan).

The idea, if I understood correctly, is that the problem should be easier to solve than the problem of reporting all intersections between line segments in general. So I'm trying to understand how hard the requirements are...


texts: Resolution and what it means to derive the empty set

texts:
When using resolution, if the empty set {Ø} is derived from a formula like {¬x,¬y} {x,y}, does that mean the formula is unsatisfiable?

If this is the case, why is {x,y},{¬x,¬y},{x,¬y} satisfiable, and

{x},{¬x},{x,y,z,w} is not satisfiable?


texts: Find the closest point in a point cloud in a near equivalent point cloud

texts:
I'm having a hard time wrapping my head around an algorithm, and not really sure if such a problem is known, common and possibly named, or if this is somewhat unique.
I have 2 different clouds of points (2D). I need to generate an index map from one to the other by proximity. Points that are closest should map to each other. This part isn't that hard.
The hard part is that each "to" point should only be used by one "from" point.
For example, let's say these are my "from" points: ([x, y] // index)
[
  [1, 10],  // 0
  [10, 10], // 1
  [19, 10], // 2
]

And these are my "to" points:
[
  [11, 10], // 0
  [9, 10],  // 1
  [10, 10], // 2
]

Then I would expect the following index mapping (fromIndex: toIndex)
{
  0: 1, // [1,10] -> [9,10]
  1: 2, // [10,10 -> [10,10]
  2: 0, // [19,10] -> [11,10]
}

In this example, all three new points are closest to [10,10], but...

The new point [10,10] (index 2) is zero distance from to old point [10,10] (index 1), so it just be assigned that index.
The new point [11,10] (index 0) is 1 distance to the old point [10,10] (index 1), and 8 distance from the old point [19,10] (index 2). index 1 is closest, but since another point is closer, the second closest point is chosen (index 2).

Finding the closest point is easy, but how would I go about finding the closest point that doesn't also have another point that's even closer, and so it should find the next closest point, which also doesn't have another point closer to that, and if does find the next closest point which... (did I go recursive?)
And obviously this would be run on point clouds of large number (up to about a max of about 50,000 at the moment)
How would I go about developing this algorithm?


texts: Is this phrase structure grammar from my textbook correct?

texts:
I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs.

On page 12, the authors start describing a set of rules that can be used to generate the set of all enumerations of names of the type "tom, dick and harry": the rules allow single names (e.g. "tom") as well as repetitions ("tom, harry, dick, dick and harry"); multiple names in an enumeration are separated by commas except the last two names which are separated by "and", so the following aren't valid: ("tom, harry, dick") or ("harry and tom and dick").

A few pages later, and after having defined some more terms and formalisms, the authors come up with the following replacement rules (parse structure grammar) to generate the sentences of the desired type:

0. Name -> tom | dick | harry
1. Sentence-> Name | List End
2. List -> Name | Name, List
3. , Name End -> and Name

In the above, Sentence is the start symbol.

However it seems to me that these rules can generate incorrect sentences: if we replace Sentence by List End and List by Name we end up with Name End for which no replacement rule is defined.

It seems to me that the 2nd line in the rules above, if replaced by

Sentence -> Name | Name, List End

would fix this problem.

Am I correct that the authors have made an oversight, and is my modification correct? Or have I misunderstood something?

I don't have a CS background and this is the first time I'm reading about parsing, so please keep that in consideration in your replies. Thanks!


texts: Given a set, partition it into ordered triples

texts:
I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$.

The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$?

I was trying to prove that this problem is NP-hard by a reduction from Numerical 3D matching (N3DM).

Given an instance of N3DM; 3 sets $X$, $Y$, $Z$, and a bound $b$, normalize it to make $b=1$. I create an instance of my problem as follows: $S=X\cup Y\cup Z$ and for each $x_i\in X$, set $a_i=x_i+3M$, for each $y_j\in Y$, set $a_j=2M-y_j$, and for each $z_k\in Z$, set $a_k=M-z_k$. $M$ is chosen very large. The idea of this comes from https://cs.stackexchange.com/a/117122/48180.

If N3DM is solved, then $x_i+y_j+z_k=1$, thus $a_i-a_j-a_k=1$ and my problem is solved. But if my problem is solved I cannot prove that N3DM is solved because I could select for example two elements from the same set say $Z$, $x_i+3M-M+z_j-M+z_k=M+x_i+z_j+z_k\geq1$ but N3DM is not solved.

I was saying maybe the problem is easy after all?

Do you have any hints?


texts: Efficient algorithms for mutual, inverse, or round-trip Personalized PageRank

texts:
I'd like to implement a similarity between two nodes (X and Y) of a graph based on a simple extension of the Personalized PageRank algorithm, either:

(Mutual PageRank): the product of the PPR of Y with respect to X and of X with respect to Y, or
(Round-trip PageRank): the probability of a resetting random walk completing a round-trip back to X after having passed through Y.

I've found some nice references for efficient PPR calculation, but I'm having trouble finding papers that optimize the search for nodes with high inverse PPR (as would be useful for the first option). If the second option has had anything published on it, I've been unable to hit on the right search term for it.

I'm not ideologically stuck to these exact definitions; I'd would be interested in references to any algorithms that are efficient and qualitatively similar.


texts: Natural deduction proof without any predicate

texts:
I am gaving trouble proving a natural deduction proof when there is no predicate given. Only conclusion is given. I understand the rules of elimnations, inclusions, IPs and others but I having trouble applying them when no predicate is given. The question is:
$$ \vdash P(a) \to \forall x(P(x) \lor \lnot(x = a))$$

Also can anyone suggest me good websites to check my proofs and practice them.  I usually use https://proofs.openlogicproject.org but in this question it is showing that its not well formed.


texts: How is it valid to use oracles in mathematical arguments?

texts: Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle".  Thus, Oracles do not exist almost by definition.  I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).  Have a problem, ask the "magic" Oracle, problem solved $O(1)$ time.  Of course you can't say anything about what is happening in the oracle, because its "magic". From this point of view, Turing Machines (bizarre fetish formalism if you ask me) with Oracles do not exist.  Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.


texts: $NL^2 = NDSPACE(\log^2n)$ is closed under complement

texts:
From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement.
From Immerman–Szelepcsényi theorem we have $NL = coNL$.

Why then $NL^2 = coNL^2$


texts: What is the name for this search algorithm?

texts:
A colleague came up with the following search algorithm:

We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$]
We are looking for the index of $i_k$ (for simplicity suppose that $i_k$ is in the array)
We suppose that the elements are pretty uniformly distributed between $i_1$ and $i_n$

The algorithm:

let "position" be initially be 0
if $i_k$ == $i_{position}$, stop
otherwise:

calculate distance = $i_k$ - $i_{position}$
if we have just switched direction (eg. the previous distance was positive and this one is negative or vice-versa), make sure that abs(distance) < abs(previous distance) by adding/subtracting 1 from distance such that it gets closer to 0. Note: if distance is already is 1 or -1, it isn't adjusted.
let position be position + distance (see note below for possible optimization)
if position is positive, let position be min(position, n) (ie. don't overshoot the end)
if position is negative, let position be max(position, 0) (ie. don't undershoot the beginning)

I would be interested if somebody studied this algorithm and if so, what's its name? The best I could come up with is that it's a variant of "interpolation search", however I expect the above algorithm to be faster on x86 hardware because it only uses addition/subtraction which is faster than the division/multiplication used by "standard" interpolation search.

Note:

Instead of updating position by adding the distance (ie. position = position + distance) we can use the "average distance between consecutive elements" as a scaling factor: $$position \leftarrow position + distance / {i_n-i_0 \over n+1}$$

This should give a more precise estimate about the element position.

A disadvantage of the above is that it involves a division which is slow(er) on x86/x64 platforms. Perhaps we can get away with finding the closes power of two to the scaling factor (average distance between consecutive elements) and use shift to perform the division (ie. if $2^t$ is the power of two closes to the scaling factor we can do $position \leftarrow position + distance >> k$.

Update:

as people have pointed out the initial element needs to be $i_0$
added steps to avoid oscillating indefinitely between undershooting / overshooting the target
discovered the "galloping search" from Timsort which seems related but not the same


texts: Find combination of array elements that exceed maximum array element

texts:
Say I have an array of integers like so:
[2,2,3,5,5,5,5,6,6,7,7,7,7,9,10]

I'd like to find all combinations of these values that when summed exceed the maximum (in this case 10) by the smallest amount (in this case a number that is closest to 11).

The function for this array would output [[9,2], [6,5], [7,2,2], ... etc]. If for example there is no possible combination that would make 11 it would try 12 and so on.

EDIT

This is not from an online course. I'm working on a hotel booking website. I have multiple rooms in the hotel, and I need to find all possible combinations for large groups. Imagine the array contains the amount of rooms by their capacity (2 x 2 beds, 1 x 3 beds, 5 x 5 beds etc...) and then I need to find all possible combinations of hotel rooms for eg. a conference of 37 people.


texts: Difference between Dependent type , refinement type and Hoare Logic

texts:
I know little dependent type theory. From wikipedia :

  A dependent type is a type whose definition depends on a value.

And from my Type theory course i recall that a dependent type is :

  Family of types indexed by a type.

But i have a confusion regarding dependent types and refinement types and hoare logic.

Because from Depenedent vs refinement type the refinement types looks like a Hoare logic. What more power refinement types gives besides just allowing to state predicated that has to be satisfied (Which looks like nearly same as Hoare Logic)?

What additional thing that dependent type gives in comparison to refinement types ? And is Dependent type more powerful than Refinement types + Sat/Constraint solver.

can anyone clear the air with examples.


texts: Prove that the class of CFG languages that are closed under reversal is undecidable

texts:
Note

The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below.

Problem Description

Given a word $w$, define $w^{r}$ to be its reversal.

Let $L=\{ G \vert G \text{ is a } CFG \text{ and for every } w \in L(G), w^{r} \in L(G) \}$

Prove that $L$ is undecidable.

My Attempt

I am aware that I should reduce a known-to-be-undecidable language to L, but by looking at the four undecidable languages here (Equivalence, Disjointness, Containment, Universality), I still failed to determine which language I can use. Please guide me a direction, thank you.


texts: Convert a polygon mesh into a b-spline surface

texts:
$\textbf{Problem:}$

Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly looks like the connected polygon mesh. It is obvious that my $\textit{b-spline}$ surface has to have a degree of one in both directions $\textit{u}$ and $\textit{v}$.

$\textbf{Output:}$

As an output for my solution. I have to generate a matrix of $\textit{control point}$ that represent that generated surface.

One property of this matrix is that each elements of each row and column are connected with each others.
If our control points matrix is a $ n \times m$ matrix, then let $C_i$ a column of this matrix with $C_i = <e_{1i}, e_{2i}, \dots, e_{mi}>$ then there must exist path in the polygon from $e_{1i}$ to $e_{mi}$.

One thing to consider if there is no edge between  $e_{ji}$ to $e_{(j+1)i}$, we can construct one as long as this edge lies inside the polygon.

$\textbf{my trivial idea}$

Assuming that the polygon has $n$ nodes. I create $n$ other nodes inside the polygon near each original node. I create then a $2 \times n$ matrix. The first row contains all the points constructing the polygon. Second row contains the corresponding additional inserted node. In order to connect two additional inserted nodes, i have to make sure that the line between two nodes is kept inside the polygon.

This idea works only for simple structure and the complexer is the polygon the hard to find these additional points.

Any good solutions maybe ?.


texts: There are algorithms to change the forms of words, to define the subject of the text, as well as the definition of his style (literary, business, scientific, etc.). Do you have any ready ideas or solutions with the help of machine learning methods to change the text style?


texts: Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior

texts:
I asked this question on Stack Overflow, but I have not obtained an actual answer to the question.

Tarjan's strongly connected components algorithm is stunningly beautiful, and inexpressible in a literal way in any programming language that I know of.

Allow me to refer to the pseudocode in the Wikipedia article. The problem is with the code that pops the strongly connected component we just found from the auxiliary stack:

// If v is a root node, pop the stack and generate an SCC
if (v.lowlink = v.index) then
  start a new strongly connected component
  repeat
    w := S.pop()
    w.onStack := false
    add w to current strongly connected component
  while (w != v)
  output the current strongly connected component
end if

The instruction w := S.pop() is unsafe, because, as far as the programming language's static semantics knows or cares, S could be empty. (Of course, a human programmer can easily tell that S will not be empty, because we are only popping S until we find v, which is initially contained in S.) Hence, a compiler for a memory safe language will emit code that

Checks whether S is empty.
Raises an exception if the stack is empty.
Pops and returns the stack's top element otherwise.

I am not too worried about the (negligible) performance impact of the useless test of emptiness. (Thus, “rewrite it in a memory-unsafe language” is not an answer.) However, I am concerned with the fact I cannot communicate an important invariant in a way that the compiler can treat as actionable information.

My questions are:

Am I overlooking some way in which I can communicate to the compiler the fact that S contains v?
If the answer to the first question is negative, is there a proof that I can't communicate this fact to the compiler?

EDIT: I am starting to suspect that the key to solving this conundrum is to use the same tricks I used to work around the lack of polymorphic recursion in SML without introducing redundant safety checks, but I need to properly write this down.


texts:
I'm reading Programming - The derivation of algorithms, and I want to understand the purpose of a predicate transformer. This is the excerpt (p. 14-15):

A more precise way in which constructs may be introduced is as follows. For each construct $S$ one defines a predicate transformer, denoted $wp.S$, which is a function from predicates to predicates. For construct $S$ and predicate $Q$, $wp.S.Q$ is interpreted as the weakest predicate $P$ for which $\{P\}\,S\,\{Q\}$ holds. It is called the weakest precondition of $S$ with respect to $Q$. The relation between the expressions $\{P\}\,S\,\{Q\}$ and $wp.S.Q$ is given by
$$ \{P\}\,S\,\{Q\}$ \text{ is equivalent to } [P \implies wp.S.Q]$$

Explain me the concept predicate transformer. What is its purpose?


texts: Computability - Can a Turing Machine calculate the input's length?

texts:
I have looked for an answer for this question which seems trivial, but I didn't find any.

  Can a Turing machine, given a word $w$, calculate the length of the word?


texts: Efficient way to calculate sum in sliding window?

texts:
Assume you have a grid as below:

The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the window should not cross the boundaries of the grid.)

For each such position I want to calculate the sum of the cells in the window.
I'd like to be able to do this with different sizes of windows as well.
More specifically, given some range for the possible widths and possible heights of windows, I want to calculate and store all the sums over the cells in the window, for all positions of the window, and for all possible width/height combinations.

As an example: if the possible widths are 2 and 3 and the possible heights are 4, 5 and 6, then there are 6 combinations: $2 \times 4$, $2 \times 5$, $2 \times 6$ $3 \times 4$, $3 \times 5$, $3 \times 6$ and for each such sliding window size, I want to store the sums over cells in the sliding window for all possible positions of the sliding window.

What would be an efficient way to do this?

Cheers


texts:
My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$):

$$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an algorithm $A$ that decides $L$} \\ \text{in polynomial time}\end{array}\right\}\,.$$

But by this definition, don't all languages belong to the polynomial complexity class? Because if I define $A$ to be 1 for all languages, then $A$ would decide all $L$ in constant time (and therefore polynomial time), since it would return 1 immediately, meaning all languages would belong to polynomial complexity.

Why is my logic incorrect?


texts: BDI logic or KARO framework solver - are there solvers for any new logic?

texts:
I am reading about agent logics and especially affective agents. There are BDI logics and combination of logics called KARO framework that considers those questions. All those logics seem to be specified and evaluated rather completely - so - are there implementation of this logics as solver or reasoner software.

If they are open source projects I would be more than happy to particiapte and contribute to them but I am afraid - Google gives nothing. Maybe there are still some projects that are hidden in the deep web and is not found by Google?

Btw. There are many logics - do they have their own solvers?


texts: Existence of a P-Complete language with space($\log\log n$) reduction

texts:
I have been reading and searching and I still cannot understand if there exists a language as following:

  Can a language be P-complete with respect to $\mathsf{Space}(\log \log n)$ reductions?

These reductions use some sort of transducer/transformer that is identical to a logarithmic transformer, except its working tape uses $O(\log\log n)$ symbols.

In other words, can the following happen?

There is a transformer with space $\log\log n$ that can reduce language A to B.
For some third language D:

D belongs to class P
For every language A in P there's a  $\mathsf{Space}(\log\log n)$ reduction to D.

I am really unsure about it. I mean, since the transformer can contain $O(\log\log n)$ symbols instead of $O(\log n)$ symbols, due to space constructibility, if $A \in \mathsf{Space}(\log n)$ then $A \not \in \mathsf{Space}(\log\log n)$? I mean if $g(n)=o(f(n))$ and $f(n)=\log\log n$, then $\mathsf{Space}(g(n)) \not \subseteq \mathsf{Space}(f(n))$, so to show such a language can exist there should be a language that can be polynomially reduced to some hard P-complete problem?

I don't understand it, especially the $\log\log n$, I think it affects the reducibility and therefore can cause a problem to create a valid transformer to show it can be reduced as needed.

Would very much appreciate if you could elaborate and show me if such language can really exist.


texts: Examples of logic gates using non-standard models

texts:
These are the only ones I have been able to find online:

Pulley Logic Gates
Marble adding machine
MARBLE COMPUTER LOGICAL AND GATE

I would like to find some more discrete models like these (as opposed to say, water logic gates or things like that). Not sure if there is a library of different techniques to build logic gates outside of electronics, or if not, what some other good examples are like these above, that perhaps demonstrate further their functionality.


texts: Heuristics & Constrain Satisfaction Problem Differences

texts:
I'm currently taking an Algorithms course, and we are covering Backtracking, CSP, and heuristics. However, I'm getting confused on exactly the differences between these terms and their applications.

When using Backtracking on a problem, I understand we are calculating the set of all allowable solutions to satisfy some property. This uses the idea of some form of constraint to make sure we can reduce the problem and not have to calculate every possible permutation.

So is the Backtracking algorithm just an application of a CSP?
But when I saw an example of solving a sudoku puzzle with the Backtracking algorithm, it took many more steps than a CSP description of it.

Also, how would the idea of using heuristics to solve a problem relate in with this?

There is a good chance I'm getting confused with some of the terminology so any advice would be greatly appreciated.


texts: Leveling array values with the smallest move

texts:
I'm not an expert of the theory of algorithm, so please forgive me if this problem is nonsense, but I want to find good algorithm to solve below problem.

There is a array of integer each of which has been assigned with random initial value such like [1,5,-3,4] or [123, 543, 295, -703, …]

You move values from one element of the array to another to achieve smaller variance. For [1,5,-3,4], the trivial final state is  [2,2,2,1].

There is a constraint. The total amount of moving distance should be as small as possible. There are many paths to move [1,5,-3,4] to [2,2,2,1], but the following way should be worse one:

move 1 from the fourth element to the first one.

[1,5,-3,4] -> [2,5,-3,3] (distance = 1 * 3)

move 3 from the second element to the third one.

[2,5,-3,3] -> [2,2,0,3] (distance = 3 * 1)

move 3 from the fourth element to the third one.

[2,2,0,3] -> [2,2,2,1] (distance = 2 * 1)

(total distance: 8)

because there is shorter (better) way to achieve this:

move 3 from the fourth element to the third one.

[1,5,-3,4] -> [1,5,-1,2] (distance = 2 * 1)

move 2 from the second element to the third one.

[1,5,-1,2] -> [1,3,1,2] (distance = 2 * 1)

move 2 from the fourth element to the third one.

[2,2,0,3] -> [2,2,2,1] (distance = 2 * 1)

(total distance 6)

What is the algorithm which can find the shortest path to level values of array?


texts:
I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.

$$L = \{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,\ m \ge 1\}$$

The grammar I came up with is:

$$
\begin{align}
S & \rightarrow aaA \\
A & \rightarrow aAc\ \vert\ bBc \\
B & \rightarrow bBc\ \vert\ bc \\
\end{align}
$$

According to the solution, this given language has an LL($2$) grammar, but the answer I came up with was LL($4$).

My reasoning is that since the start of the language has at least three $a$'s, you need to check the fourth position in order to see which production to use afterwards. Then you can "slide" the window one position to the right to check subsequent productions.

Why is it considered LL($2$)?

Thank you.


texts: Longest palindrome after swapping operation

texts:
I know that Manacher's algorithm can be used to find the longest palindromic substring of a string in linear time.
But I want to find the longest palindromic substring after swapping any two indices once.
If I run a for loop twice in $O(n^2)$ to find all possible swaps and find the max of all formed strings I get the ans but in $O(n^3)$.
Is there a better way like $O(n)$?


texts:
Referring to these notes regarding DFS - Click Here

They refer to the following claim that follows Definition 0.2. as observation:

  A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher.

However, I don't really understand why is that obvious or how can it be proved.

I'd appreciate a proof of this claim.


texts: Seeking nontrivial small SAT/UNSAT instances

texts:
I need SAT instances, involving 9 to 20 variables. They need to be hard to solve for humans. Both SAT and UNSAT instances are needed.

I tried random-SAT generators on the web, but the results were not satisfactory because they are trivial. A good example of what I'm looking for is the following 4-variable instance from The Art of Computer Programming: $$12\bar3, 23\bar4, 134, \bar124, \bar1\bar23, \bar2\bar34, \bar1\bar3\bar4, 1\bar2\bar4.$$


texts: Understanding connection between different database concurrency control protocol

texts:
I have came across following diagram related to timestamp based concurrency control protocols in database systems:

I don't know whether its correct or not.

As per my interpretation, it means all schedules possible under protocol of particular oval is also possible under protocol of enclosing oval.

However as long as I know, both multiversion timestamp and timestamp ordering protocols ensures conflict serializability, whereas Thomas write rule ensures view serializability.

So I guess, the diagram correctly depicts the relation between Thomas write rule and timestamp ordering protocol. But I am unsure whether it correctly depicts the relation of multiversion timestamp ordering protocol correctly in relation with Thomas write rule. (I believe relation between multiverstion timestamp ordering protocol and timestamp ordering protocol is also correctly shown).

Should it be something like this:

I have came with above diagram because I feel it correctly captures following points:

All schedules possible under timestamp ordering are also possible under multiversion timestamp
All schedules possible under timesstamp ordering are also possible under thomas write rule
Some schedules (specifically view serializable ones) possible under Thomas write rule are not possible under multi version timestamp protocol and vice versa (schedules involving different versions of data items).

Am I right with all of these?


texts: PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

texts:
Can someone help with this
$L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$


texts: Train a neural network to play tic tac toe using a genetic algorithm

texts: I have an assignment for school, in which I have to build a neural network that will play tic tac toe, using genetic algorithms for training. The thing is that I am clueless on how to connect the two. I need help in the design. Should use the GA to generate game boards, to serve as input for the neural network. Or, should I generate the NN weights with the GA. In both cases. I'm having a really hard time with this subject, but I find it extremely fascinating. Any help would be much appreciated. Thanks


texts: Fast polynomial calculation over $\mathbb{Z}_{487}$

texts:
Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}_{487}$, I'd like to choose distinct values $x_0, x_1, . . . , x_{242} ∈ \mathbb{Z}_{487}$, such that I'll be able to calculate $a(x_j )$ for all $j = 0, . . . , 242$ by calculating three polynomials $a
_0 (x), a_1(x), a_2(x)$ of degree at most $80$ for $81$ different values of $x$.

So first of all I divided $a(x)$ into sub-polynomials, simply by:
$$\begin{align*} a(x)=x^{162}\cdot&\left( a_{242}\cdot x ^ {80}+...+a_{163}\cdot x+a_{162} \right)+\\
& x^{81}\cdot\left( a_{161}\cdot x ^ {80}+...+a_{82}\cdot x+a_{81} \right)+\\
&\left( a_{80}\cdot x ^ {80}+...+a_{1}\cdot x+a_{0} \right)\end{align*}$$

Now I have shown that $2^{243} = 1 \mod 487$, and that for every $1\leq a \leq 242: \,\,\, 2^a \neq 1 \mod 487$.

I wanted to use this so that I can choose distinct $x_i$ by $x_i=2^i \mod 487$ for all $0\leq i \leq 242$. Now I thought taking triples, and for that I had two ideas:

Choose triples $x_i,x_{i+1},x_{i+2}$ for each $0\leq i\leq 242$ such that $i = 0 \mod 3$.
Choose triples $x_i,x_{i+81},x_{i+162}$ for each $0 \leq i \leq 80$.

In any case, given a trio, I wanted to calculate only $a_2(x_i), \,a_1(x_i), \,a_0(x_i)$, and then using them to calculate $a(x_i),\,a(x_{i^{'}}),\,a(x_{i^{''}})$, where ${i^{'}} $and ${i^{''}}$ will be the next in my trio (depending on which idea to choose).

The problem is, I either got confused and all that's left is obvious, or I just can't seem to make those last few steps. If Im on the right way, can someone help me here? Or perhaps I should choose other trios? Or if not, maybe there's a hint that can help me out?


texts: Prove lower bound of searching algorithm on Young Tableau

texts: I want to prove the search of an element in a Young tableau of size $n\times n$ is $\Omega(n)$, but I do not have any clue. Any help is appreciated!


texts: Pros and Cons of Average Memory Access Time When Increasing Cache Block Size

texts:
Assuming we have a single-level (L1) cache and main memory, what are some of the advantages and disadvantages of having a larger cache block size (considering average memory access time).

The only ones I can think of are that a larger block size could increase the hit rate when adjacent memory locations are accessed, i.e. good for spatial locality. I can't think of any other advantages; are there?

As for disadvantages, I assume that having a larger block size increases the cache size, thereby increasing cost (since L1 cache is expensive), but I can't see any disadvantages relating to average memory access time. Are there?


texts: Can Breadth-First Search be Implemented Recursively without Data Structures?

texts: I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through a maze. Is there a way to do this just using the basic structure of recursive calls and base cases? Or will I need data structures such as queues or stacks to implement breadth-first recursion?


texts: Must every NP-Complete Problem have a class of instances which is solvable in Poly time?

texts: Is there any theorem that states that any NP-Complete Problem has a class of instances solvable in Poly time? For example, some problems like vertex cover are NP-Complete on general graphs but can be solved in polynomial time on instances which are Trees. Does every NP-Complete problem have such class?


texts: Reconstructing Graphs from Degree Distribution

texts: Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph can be constructed and any one example if multiple graphs can be constructed.


texts: Is L={|M is a TM and L(M) is uncountable} decidable?

texts:
Is $L=\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\}$ decidable?

My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is not decidable, how can I prove that using reducibility?


texts: Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

texts:
I have a min heap.

I need to find the 7'th biggest value in the heap with $O(1)$.

I need to build the algorithm.

I dont realy have an idea how to get to this efficiency.

Help?

Thanks.


texts:
I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as -

Let # of states in the FA be n & I select the string w = a^2n
Now let xyz = w
xy = a^n
y = a^m | m is odd number
now x(y^2)z = a^(n-m)(a^2m)(a^n)
= a(2n+m) does not belong to L

which says this regular set doesn't satisfy pumping property. Please let me know if I am doing something wrongly.

Thanks in advance.


texts: Calculating the set field of associative cache

texts:
In this example:

Assume a system’s memory has 128M words. Blocks are 64 words in length
and the cache consists of 32K blocks. Show the format for a main
memory address assuming a 2-way set associative cache mapping scheme.
Be sure to include the fields as well as their sizes.

The following is supposed to be the solution:

Each address has 27 bits, and there are 7 in the tag field, 14 in the
set field and 6 in the word field.

I understand how the word field was calculated (2^6 = 64), but I don't understand how is the set field 14?.
Shouldn't the answer be 8?
Block size is 64 words, to find the number of sets we divide total number of blocks 32K by set size which is 64*2=128B (multiply by 2 since it's 2-way), my calculation should be correct, am I missing something?

32KB/(64*2)B = 32KB/128B = 256 = 2^8
(Which implies that we need 8 bits for the set field)


texts: Future register file in computer architecture

texts:
Results from the execution units are written into the future file when they complete (may be out-of-order). Upon operand fetching, you fetch from the future file and not the architectural register file.
But what happens in this case:

FADD R3, R2, R1
ADD R3, R6, R7
...
SUB R9, R3, R9

the FADD is a floating point add and takes multiple cycles to handle. It finishes later than the ADD so is that result the one that is found in the future register file? The SUB instruction fetches its operands from the future file thus getting the wrong value of R3?


texts: Is there a formal definition of "data structure"?

texts: Data structure is a term that I've heard use I think only somewhat informally in software engineering. Is there a formal definition of it in CS?


texts:
I was introduced in concurrency programming this morning.
I haven't understood why "non deterministm" is a fundamental aspect of cuncurrenty programming.

What i think is that, since there is a scheduler (so an algorithm) i deterministicly know the order of the tasks


texts:
The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach is exponentially fast) an infeasible number of repetitions may be required before we have a significant probability of confidently distinguishing satisfying inputs from non-satisfying ones. Nevertheless, PP is an interesting complexity class to study in its own right.

Is there a similar well-defined complexity class "QPP" of problems which a quantum computer has a greater than 50% chance of correctly solving in polynomial time? I understand that if so, this class of problems would not be feasible on a quantum computer, but are any nontrivial inclusions with the more "traditional" complexity classes either proven or suspected? How "big" do we think the class QPP is?


texts:
Studying for my qualifying exam, have a past exam here, which has the following question, verbatim:

  Give a proof of the Folklore statement: "sequential space is parallel time." In other words, the space used by a sequential algorithm for a problem $X$ can be equated (within Big Oh) to the time taken by a parallel algorithm for $X$.

However, in the textbook I have, I haven't found a good definition for a sequential algorithm or parallel algorithm, which is necessary if I'm going to prove anything.  Also, googling turned up the wikipedia page  on parallel computation thesis
but it seems to depend on the model of computation used.  So I'm not sure how to answer this question.


texts: How to handle the repeat until convergence condition in time complexity and summarize the time complexity?

texts:
I am a novice in complexity calculation. I need to calculate the overall time complexity.
My attempt is given below:
Here, N = number of data points (N>300), C = Number of clusters (2<C<30)

For line 3 to 10, time complexity, TC1 = O(NC)

For line 11 to 12, time complexity, TC2 = O(C)

For line 18 to 22, time complexity, TC3 = O(N*N)

For line 24 to 26, time complexity, TC4 = (how to handle the repeat until convergence- the highlighted section?) (Here, I think TC4 = O(N*N))

For line 16 to 29, the overall time complexity, TC5 = C(TC3+ TC4) = O(N*N*C)// not sure about it due to the lacking confidence in the value of TC4.

For line 31 to 35, time complexity, TC6 = O(N*C*C)

For line 38 to 40, time complexity, TC7 = O(NC)

So, finally, the overall time complexity TC = TC1 + TC2 + TC5 + TC6 + TC7 = O(NC) + O(C) + O(N*N*C) + O(N*C*C) + O(NC) = O(?) //How can I summarize this time complexity using Big-O.

My Questions are:
a) How to handle the highlighted portion when calculating the time complexity?
b) How to summarize the overall time complexity?

Please help.


texts:
A function $T: \mathbf{N} \rightarrow \mathbf{N}$ is time constructible if $T(n) \ge n$ and there is a Turing Machine $M$ that computes the function $x \mapsto \lfloor T(|x|) \rfloor$ in time $T(n).$

Here $\lfloor m \rfloor$ denotes the binary representation of $m$ for a natural number $m$.

I understand that $T(n) \ge n$ is required in order to give the $M$ sufficient time to read its input. About the mapping $x \mapsto \lfloor T(|x|) \rfloor$: since $x$ is a natural number, does this mean $|x|$ is the number of digits in the decimal representation of $x$?

As an example, let's forget about the the requirement that $T(n) \ge n$. Suppose $T(n) = \log_2 n$. Then, for example, $T(2^{100}) = 100$, but what is $T(|2^{100}|)$ in this case?


texts: Analysis of sorting Algorithm with probably wrong comparator?

texts:
It is an interesting question from an Interview, I failed it.

An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order).

We have a comparator $C$, but it has a probability p to return correct results.

Now we use $C$ to implement sorting algorithm (any kind, bubble, quick etc..)

After sorting we have $[A_{i_1}, A_{i_2}, \ldots, A_{i_n}]$ (It could be wrong)。

Now given a number $m$ ($m < n$), the question is as follows:

What is Expectation of size $S$ of Intersection between $\{A_1, A_2, \ldots, A_m \}$ and $\{A_{i_1}, A_{i_2}, \ldots, A_{i_m} \}$, in other words, what is $E[S]$?
Any relationship among $m$, $n$ and $p$ ?
If we use different sorting algorithm, how will $E[S]$ change?

My idea is as follows:

When $m=n$, $E[S] = n$, surely
When $m=n-1$, $E[S] = n-1+P(A_n \text{ in } A_{i_n})$

I dont know how to complete the answer but I thought it could be solved through induction.. Any simulation methods would also be fine I think.


texts: How can I find the perplexity of a text by the perplexity of its sentences?

texts: For a bigram language model, I can calculate the perplexity of sentences of a test document. However, I'm not sure what would be the perplexity of the whole document. Should I get the average of the perplexities of sentences?


texts: Is the Projection Matrix estimated using least-squares pose specific?

texts:
I am calibrating a camera and estimating the projection matrix using the least-squares technique described here.

So far, I thought that the projection matrix that I got with this method was invariant, e.g., I could use it disregarding if the camera was moved or not.

However, I have been doing some additional reading, and I came across a set of slides that led me to believe that, if the camera is moved, then I'd have to estimate the projection matrix all over again.

Can someone please clarify this?

Thank you.


texts: Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

texts: With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is the same as Huffman coding. However, I'm not sure how to prove that arithmetic coding with this restriction is optimal for integer code lengths.


texts:
I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-heaps to implement the A* algorithm. In these cases, we do not need to construct the search tree explicitly.

But I can not find a simple data structure to simulate the searching process of the AO* algorithm. I would like to know if constructing the search tree explicitly is the only way to implement AO* algorithm? Can anybody provide me an efficient implementation?


texts: Optimal Algorithm for Finding Maximal Number of Colinear Points

texts:
Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line).

The crudest algorithm is to compute the slope and intercept of each pair of point, assuming infinite precision, find maximal number of appearance of the same pair of parameters.

Is there an algorithm more efficient (1) in the worst case, (2) on average? What is the optimal one (1) in the worst case which I suspect the crude method with complexity $n\choose 2$ is the optimal, (2) on average; and how to prove it?


texts: For dynamic programming problems, how do we know the subproblems will share subproblems?

texts:
So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when:
Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.
So my question is that how do we know when in a problem if we apply the divide-and-conquer approach, we will get overlapping sub-problems?
Eg:
Let's take the famous problem from Cormen.

A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting, and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

Here, how do we know that subproblems will overlap?


texts: Guess the number from its different base representations

texts:
Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or return no number exists.

Constraints given: $2\leq base \leq 36$, No. of numbers given in different representations is N $\le$ 100, Test Cases $\leq$200, time Limit 1sec

For example,

Here $T=1,N=3$,

$1001111$

$117$

$4F$

These all represent the same number, i.e $(79)_{10}$. $(1001111)_3$ = $(117)_8$=$(4F)_{16}$ Hence answer is $79$. Whereas if any of the above number is changed to any other except those (for eg. if (1001111) is changed to something else) then the answer would be "No such number exist".

Please suggest an Efficient way with a pseudo code/code.


texts:
I was reading a book which describes a historical perspective:

Pentium 4E (2004, 125 M transistors). Added hyperthreading, a method to run two programs simultaneously on a single processor, as well as EM64T, Intel’s implementation of a 64-bit extension to IA32 developed by Advanced Micro Devices (AMD), which we refer to as x86-64

I'm a little bit confused here, here are my two questions:

Does it mean that 'x86-64' is just an alias of 'EM64T'?

Is IA32 developed by AMD? Isn't IA32 designed by Intel and first implemented in the 80386 microprocessor in 1985? See Wikipedia.


texts:
I'm trying to understand the reduction as a flowchart graph.

Let's say the boxes $A$ and $B$ are TMs/Functions and $x$ is the input.
Is this plot represent reduction from $A$ to $B$ ($A\le B$) or from $B$ to $A$ ($B\le A$)?
Or maybe it can be both of the way depending on the context?


texts: How can I compare by this two algorithms?

texts:
I have two algorithms has a complexity of O (n log n) and the B-complex algorithm (n^2). By imposing NA size the larger issue that a algorithm can solve in a given time and NB size the larger issue that the B algorithm can solve in the same time on the same machine. Prove that NB < NA.

How can I solve this question ?
Thank you


texts: Construct a digraph given its in-degree and out-degree distribution

texts:
Could anyone help me with this algorithmic problem:

Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph can allow self loops but not parallel edges.

Here's an example:

Vertex A: in=1 out=1
Vertex B: int=2 out=2

For which we can construct this graph:

A => B
B => A
B => B

Here's another example:

Vertex A: in=0 out=1
Vertex B: in=1 out=1

Here, we obviously cannot construct such graph.

I have been scratching my head around this problem.
For an undirected graph, there exist a simple algorithm to solve this problem but I cannot find any way to derive a solution for directed graphs.

I have the intuition that we could find a matching algorithm in the bipartite graph representing the in and out edges of the graph and where each out-edge would be matched to an in-edge.

However the usual approach can produce a graph with parallel edges.

For example 1, a valid solution could be:

A- A+: A => A
B- B+: B => B
B- B+: B => B

Which is not a valid graph.

Also, please note that I am more interested in determining if a valid solution exists. It's not necessary to provide or construct such solution.


texts: Is the language $\{ 0^m 0^n : 0 \leq m \leq n\}$ regular?

texts:
Is the following language regular?
  $$ \{ 0^m0^n : 0\le m\le n \}. $$

According to me, it is not regular. However, some of my friends are arguing that every string in $0^*$ can be divided into $0^m0^n$ satisfying the constrains between $m$ and $n$, hence it is regular.

Although I am absolutely sure that their reasoning is false, they are thinking in reverse, I would like a third opinion.

Here is my proof of non-regularity:

Let us take $0^p0^{p+1}$ as a string.

Applying the pumping lemma, we find that the part with $0^p$ needs to be pumped. So, even if it is pumped by one 0 at a time, we will soon get $0^{p+2}0^{p+1}$, which violates the constraints between $m$ and $n$.


texts:
I'm writting a compiler implementation for a language that you can see defined here. I having problems designing how the do keyword should be handled. You can find the code I'm referring to in here.

Let me delve a little bit into the problem. According to the documentation:

  The do keyword is used to call an expression (normally, a method call)
  just for its side-effect, and discards the result.

Now according to the list of possible expressions in the file I referred to before:

IntLit(value)
StringLit(value)
True()
False()
And(lhs, rhs)
Or(lhs, rhs)
Plus(lhs, rhs)
Minus(lhs, rhs)
Times(lhs, rhs)
Div(lhs, rhs)
LessThan(lhs, rhs)
Not(expr)
Equals(lhs, rhs)
ArrayRead(arr, index)
ArrayLength(arr)
MethodCall(obj, meth, args)
Variable(Identifier(name))
New(tpe)
This()
NewIntArray(size)

I want to figure out first in which cases should do act. Clearly, it should act with MethodCall as it provides a result but also with expressions that contain operators (And,Or,Plus,Minus,Times,Div,LessThan,Not,Equals,...). What would be the complete list of cases I should consider?

My second question is how can I implement Do behaviour for MethodCall, that is, not getting the result but getting the side effects.


texts:
http://jgaa.info/accepted/2011/HasheminezhadMcKayReeves2011.15.3.pdf
 Hello I stumbled upon this paper. On page $4/20$ the figure shows an infinite sequence of $5-$regular, connected planar graphs. But they do not define it rigorously. The first graph of the sequence is clearly the icosahedron, and I feel that the next ones are constructed by "gluing" copies of $D_1$ but the only way I thought of constructing $D_k$ from $D_{k-1}$ and an icosahedron, would be removing a vertex from the border of its outer face. Then we remove a vertex from the border of the outer face of a copy of icosahedron and then we connected the vertices of degree $4.$ But this would leave us with less vertices than the graphs shown there.
 Is my construction ok? Also which procedure gives us the sequence shown on the article?
 thanks in advance.


texts:
I am new to machine learning. But have basic understanding of the concepts.

Problem statement : We humans won't perceive much difference between "Tim Cook" and "Tim C0ok". ( 0 is been replaced with zero ). I am trying to model this.

Task is to come-up with a model which can predict if two names are visually similar. The system will be configured with a predefined set of names. When the system is online, it should predict whether a given name is similar to one of the configured name or is not similar to any of the configured name.

My current approach: I'm trying to come up with a two-stage model. First stage is a binary classier which predicts name is know to system or not. Second stage is a multi-class classifier, which tells to which configured name given name is similar.

Features : Using string distance measures Levenshtein Distance, Damerau-Levenshtein Distance, Jaro Distance, Jaro-Winkler Distance and Hamming Distance as the feature vector. Feature vector is computed between a reference string ( Ex : 'aaaaaaaaa' )  and the name.


texts: Find multiple duplicates in $n$ size data set in linear time

texts:
Problem:

  Given a vectors of size $n$ with integer data within $[1, n-1]$ range, find $if$ and $which$ numbers are multiple duplicates (numbers appearing more than once). The time complexity ought to be linear and space complexity constant (don't use any auxiliary data structure except the input vector and variables) and the input data set ought not to be modified.

I'm trying to solve this problem for at least one multiple duplicate (as a starting point, although I don't know if the solution to this case can be expanded to the general case of at least two multiple duplicates). Here's what I've done so far:

The $if$ part is relatively easy, taken we can be proven using the pigeonhole principle to show that there $will$ be at least a simple duplicate within the given data set.

The $which$ part, on the other hand, is what gives me headaches. Unlike  the missing number problem, we cannot simply Xor the numbers. Neither can we sum them up and subtract the sum from 1 to n-1, thus finding a simple duplicate. Can anyone suggest a good approach towards this problem?  You are not allowed to modify the input array.


texts:
here is a competitive programming question:

You have a number of chores to do. You can only do one chore at a time and some of them depend on others.
Suppose you have four tasks to complete. For convenience, we assume the
tasks are numbered from 1 to 4. Suppose that task 4 depends on both task 2 and task
3, and task 2 depends on task 1. One possible sequence in which we can complete the
given tasks is [3,1,2,4] - in this sequence, no task is attempted before any of the other
tasks that it depends on. The sequence [3,2,1,4] would not be allowed because task
2 depends on task 1 but task 2 is scheduled before task 1. In this example, you can
check that there exactly three possible sequences compatible with the dependencies:
[3,1,2,4], [1,2,3,4] and [1,3,2,4].
In each of the cases below, you have N tasks numbered 1 to N with some dependencies
between the tasks. You have to calculate the number of ways you can reorder all N
tasks into a sequence that does not violate any dependencies.

[Task, Dependency(s)] : [1, NA], [2,1], [3,2], [4,1], [5,4], [6, 3 and 5], [7,6], [8,7], [9,6], [10, 8 and 9].

I inferred the following:

Any sequence will always start with 1, since it has no dependencies.
6 will always be in the 6th position of any sequence.
10 will always be at the last position.

Then, by trial and error, and listing all possibilities for the two separate parts of the sequence (1 _ _ _ _ 6 and 6 _ _ _ 10), I got 6x3 = 18 possibilities. However, for a larger set of data, these deductions would not be easy. What is the way to calculate this logically and find the number of possibilities, and how can this be integrated into a program?

(I have tried to represent the question as clearly as possible, but you can visit this link to view the question (Q. No 4): http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf)

I am a high school student preparing for a programming competition, and I haven't taken many courses on algorithm design, so this might be a trivial question - please excuse me!


texts: Simplifying the Boolean expression $A + \bar{A}\bar{B}$?

texts:
So I'm trying to simplify the Boolean expression (1) $A + \bar{A}\bar{B}$.

I noticed that by Karnaugh maps this is equivalent to $A+\bar{B}$, and I also noticed that if I take the complement of (1), I get ~(1)= $\bar{A}(A + B) = \bar{A}A + \bar{A}B = \bar{A}B$, so then taking complements again yields (1) = $A + \bar{B}$.

But this feels very ad hoc to me, and makes me feel like I'm missing some key point about how to simplify this expression more systematically.

Any thoughts appreciated.

Thanks.


texts: Practice question on the applications of flows and cuts

texts:
This question is from Erickson's textbook on algorithms, p. 376, question 18.

  Faced with the threat of brutally severe budget cuts, Potemkin University
  has decided to hire actors to sit in classes as “students”, to ensure that every class they offer is completely full. Because actors are expensive, the university wants to hire as few of them as possible.

  Building on their previous leadership experience at the now-defunct Sham-Poobanana University, the administrators at Potemkin have given you a directed acyclic graph $G = (V, E)$, whose vertices represent classes, and where each edge $i \rightarrow j$ indicates that the same “student” can attend class $i$ and then later attend class $j$. In addition, you are also given an array $cap[1\cdots V]$ listing the maximum number of “students” who can take each class. Describe an analyze an algorithm to compute the minimum number of “students” that would allow every class to be filled to capacity.

My best solution is $O(cV^3)$, where $c$ is the max of class capacities $\max_i \{ cap[i] \}$. Is there a better solution? Because I have a feeling there is.

My solution:

Initialise $x$, the minimum number of students to fill each class to capacity, as 0.
For each vertex $i, j$ where $i \neq j$, combine all the $i \rightarrow j$ edges into a single edge with capacity equals the number of original $i \rightarrow j$ edges.
Set the capacity of each vertex $v$ as $cap[v]$.
Since this is a DAG, there are source vertices and sink vertices. Add a vertex $v_\text{in}$ with outgoing edge of infinite capacity to each source vertex. Add outgoing edge of infinite capacities from each sink vertex to a another new vertex $v_\text{out}$.
Find the max $(v_\text{in}-v_\text{out})$ flow. $|f|$. Increment $x$ by this value $|f|$. Decrement the capacity of each vertex and edge in the graph by the component flow through it.
Remove $v_\text{in}, v_\text{out}$, and their edges. Remove all vertices and edges with capacity zero.
Repeat steps 4 to 6 until no vertices are left in the graph.

Time complexity:

This solution runs Orlin's $x$ times, but $x$ is bounded from above by the maximum of class capacities, previously denoted $c$. So, $O(cVE) = O(cV^3)$.


texts: Basic second-order logic example contains a mistake?

texts:
I'm reading the following course on second-order logic, by Péter Mekis :
http://phil.elte.hu/mekis/sol.pdf .
The course seems excellent, but I'm stuck on one of his first examples for showing the power of second-order logic w.r.t first-order logic.

In this example, he works on the following statement : "Santa Claus has all characteristic properties of a pedophile."
This is translated into the second-order logic sentence : ∀X ( R(X,P)→P(a) ),
where a is santa, P is the property of being a pedophile, X is a property and R tells us whether a property is characteristic of another property.
I understand this as : for all properties, if a property is characteristic of being a pedophile, then santa is a pedophile. This is obviously not what the statement says, so am I misunderstanding or should the second-order logic sentence instead be : ∀X ( R(X,P)→X(a) ), effectively meaning : for all properties, if the property is characteristic of being a pedophile, then santa has this property.


texts: Generating context-free grammar from a language

texts:
Consider this language
$L=\{a^n b^m c^k | k \neq n+m\}$
Can somebody tell what is the context-free grammar of L?


texts: How to interpret this context free language?

texts:
$S \to aAA$
$A \to aS \mid bS \mid a$
Trivial thing:
starting and ending with a
Atleast 3 a's are definitely present
(These are very layman observations...but seriously I am unable to figure out what exactly this language is all about. ...)
My attempt:
What I am able to generate
1)aaa
2)aAA
a bS A
a ba AA A
a ba ***
This suggests after b there should be atleast 1 a
*(Coz those *** have all

a's

or

if bS used then again a 'ba**'

Or

if aS used length also increases by atleast 3.)*

I know this is not a good analysis..and so I am not expecting any answer but would definitely expect some comments about some intuition or idea..plz any help would be much regarded..
(Although answers are always welcome ;-) )


texts: How many iterations of Lanczos bidiagonalization are required in order to obtain the first k singular values/vectors of a matrix?

texts:
I am trying to implement a fast SVD algorithm for obtaining the first $k$ singular values/vectors of an $M\times N$ matrix ($k < \min(M,N)$) using the following 2-step process:

1) bidiagonalize the matrix using Lanczos bidiagonalization (e.g. R. M. Larsen, 1998)

2) diagonalize the bidiagonal matrix via QR decomposition or divide and conquer algorithm.

Here is where I am confused. My understanding is that the first step (Lanczos bidiagonalization) is the most expensive step. Therefore, I should perform as few Lanczos iterations as possible in order to keep the algorithm fast/efficient. Since I am only trying to find the first $k$ singular values/vectors, my initial thought was that I only need to perform $k$ iterations of Lanczos bidiagonalization (i.e. recover only the first $k$ Lanczos vectors). If I do this, and then take the svd of the resulting bidiagonal matrix, I find that only the first couple singular values are accurate. This leads me to believe that if I want to compute the first $k$ singular values/vectors accurately, I need to perform $L$ iterations of Lanczos bidiagonalization ($L>k$) in order to obtain reasonably accurate singular values. For example, choosing $L=2k$ seems to produce reasonable results for the few tests I have done.

Is there a technique or rule of thumb for choosing a reasonable number of Lanczos iterations?


texts: How the conditional random fields algorithm work?

texts:
Im searching about conditional random fields for a long time and cant understand the concepts of this algorithm.

I understood markov chains, and understood that conditional random field is a more complex modification of markov chain, Im right?

So, what is the best didactic explanation of conditional random fields?


texts: Having trouble understanding Red-Black trees

texts:
Exam question:

Draw the Red Black Tree that results from inserting the following
values in the given order:
[10, 20, 30, 4, 5, 50]
Draw the red connections with a dotted line and the black ones with a continuous line.

What I understand about Red Black Trees:

Every node is either red or black.

The root and leaves are black.

If a node is red, then its parent is black.

For every leaf, the path has the same number of black nodes (the tree is balanced).

My profs solution:

Solution from this website

I'm very confused as to how to solve this, my prof's PPTs say that all the red connections are to the left, I've found places that say that all reds are to the right, others where it's irrelevant.
Can someone explain how to solve this?


texts: Comparing Directed Unweighted Graphs with Different "Densities"

texts:
I'm looking to compare 2 unweighted directed graphs and get an (ideally differentiable) similarity score. Both graphs describe a trajectory in a 2d space.
The reference graph is a step by step guide to an end location. The nodes have a value which corresponds to a precise action such as forward 1m, left 30 degrees. The edges are only used to link steps together.
The comparison graph nodes on the other hand only contain directions rather than precision instructions (e.g. left, right, forward). Similarly the edges have no information.
While both graphs contain similar information,the comparison graph contains far fewer points (2-10x). I first tried reducing the reference graph to the same direction level by compressing multiple nodes of the same value together. This works somewhat, but leaves a lot to be desired. It is still too "low-level" to be directly comparable.
I'm in the process of evaluating edit distance (specifically a soft variant) and nDTW as possible candidates.
My questions are:

What other metrics exist to compare graphs of this nature? I've looked at some slides and a survey on graph comparison and while these were helpful, I don't have enough intuition to choose between the methods they propose.
Are there other ways of comparing these 2 sequences, besides treating them as graphs?
Is there a community that might have a similar need? Like bio-informatics?


texts: OOP: exampe and references on constructor anomalies

texts:
I have read the following artice that defines the term "constructor anomaly":

Cohen, Tal, and Joseph Gil. "Better Construction with Factories." journal of object technology 6.6 (2007): 103-123.
http://www.jot.fm/issues/issue_2007_07/article3/

Where can I find examples and references on constructor anomalies? (also in the context of multiplie inheritance)

Are constructor anomalies always due to a method call in the constructor or is it possiple to construct an example without method calls in the constructor?


texts:
A boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$.
It is known that every boolean function is in $\mathrm{NC}^1$, i.e. there is a circuit of depth $O(\log n)$ computing it.
What is known about the constant inside the $O()$ notation? Specifically, can one construct, for every $c$, a symmetric function requiring a circuit of depth at least $c \log n$? Or there is some constant $c_0$ such that every symmetric function has a circuit of depth at most $c_0\log n$?


texts:
in many lecture notes, I have seen the LTL idempotent law for until and its equivalence is described as $\phi U(\phi U \psi) \equiv \phi U\psi$ and also $(\phi U \psi)U\psi \equiv \phi U \psi$
. Also by definition of $G$, some formula holds in every state. So if globally $\phi$ holds until we see $\psi$ does it make every state after it true? question might sound weird but by formula  is it correct to say that also $G(\phi U \psi)U\phi \equiv G(\phi U \psi)  $


texts: Finding the best N length combination between M items

texts:
Lets say I have a few million random items. Each item has 6 attributes: Type, Cost, Strength, Stamina, Agility and Intelligence. Type is one of 4 different possibilities, the other 5 are various numbers

Now I must produce a set of 4 items where the inputs are X (the maximum cost of all items) and Y (one of the latter 4 attributes that is favored) so that

Each of the types is present exactly once
The total cost must be below a certain amount (X)
The attribute determined by Y must be the highest among all possible combinations

Currently I'm doing this in a brute force manner, just trying every single combination and comparing it to the current best result but its very time consuming. I was wondering if anybody knows of an algorithm or something that would cut down the execution time?


texts:
I need to train SVM with 2 different features..the problem is one feature is the HOG with length 144 and other an RGB value with length 3.. Can i combine these two features to train SVM  and test using the same? the code iam using is

X1=xlsread('train1.xlsx');
Y1=xlsread('CLASS1.xlsx');
svmStruct1=svmtrain(X1,Y1);
 classes=svmclassify(svmStruct1,test);

the test data contains both RGB and HOG values..


texts:
Given an array $A[1],\ldots,A[n]$ of natural numbers, we have to construct a new array $B[1],\ldots,B[n]$, where $B[i]$ is equal to $A[j]$ for the minimal $j > i$ such that $A[j]$ divides $A[i]$, or $-1$ if no such element exists. For example:
$$
\begin{array}{c|ccccccc}
A & 10 & 4 & 5 & 2 & 1 & 8 & 4 \\\hline
B & 5 & 2 & 1 & 1 & -1 & 4 & -1
\end{array}
$$

I can solve this in $O(n^2)$ using brute force. Is there a better solution?


texts: How can a Turing Machine recognize a regular language?

texts:
This is a practice problem for a midterm in a class I'm taking:

  Given a regular language $L$, describe formally a Turing machine that recognize $L$.

I'm not sure how I should do that.


texts: Shortest path from source to all vertices, but with some wildcards

texts:
Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).

You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated with it. Vertex $1$ is source vertex. You have $K$ wildcards. In the path from vertex $1$ to vertex $i$ ($2 \leq i \leq n$), you can use at most $K$ wildcards while traversing. When you use a wildcard on an edge, you can pass that edge in summing the cost of path (i.e., value of that edge will be $0$ if you use a wildcard on an edge). Note: You can use at most $K$ wildcards from vertex $1$ to vertex $2$. Now you can again use at most $K$ wildcards from vertex $1$ to vertex $3$ and so on to vertex $n$. In other words, you can use at most $K$ wildcards in each path from source to destination. You have to find minimum distances from node $1$ to all other nodes in graph.
Constraints: $1 \leq n, m \leq 500000, 1 \leq K \leq 15$
Expected Approach: DP with shortest path algorithms on graph.

What I am doing is that, we can choose $k$ edges from $m$ edges in $\binom{m}{k}$ ways. And for each case find shortest path, but that will be too much time complexity.


texts: Regular expression for odd binary numbers without leading zeros

texts: I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^*1$, but that doesn't match just 1. The best it matches is 11.


texts:
I have a practice exam question that I am looking for help with. It is regarding proving NP-Completeness using Reduction. The problem is as follows:

The Set Cover problem is the following:

Instance: A set $U = \{1,2,...,n\}$ of $n$ elements, a collection of subsets $S_1,S_2,...,S_m$ of U, and an integer $K$.

Question: Are there $K$ sets among the $S_i$’s whose union is equal to $U$?  In other words, are there $K$ sets which together cover all the elements of $U$?

Prove that Set Cover is NP-complete

Any guidance here would be greatly appreciated. My thought is that I should try reducing from the Vertex Cover problem, but I am not entirely sure how to reduce from there.


texts: If $f(n)$ is $O(g(n))$ is it also $O(g(n-d))$?

texts:
When trying to prove that a recurrence $g(n)$ satisfies $g(n) = O(f(n))$, we sometimes are not able to find a valid $C$ to show the upper bound, so we try to prove it is $O(f(n-d))$ for some constant $d$ instead.

If we are able to prove that $g(n) = O(f(n-d)$, does this mean that it is also $O(f(n))$?
If so, does this go the other way too? That is, if $g(n)=O(f(n-d))$ for some $d$, then $g(n) = O(f(n))$ as well?

edit 1:
Here a valid $C$ means, $C$ such that $f(n) <= C*g(n)$ for all $n > n0$ for some $n0$


texts: Recursive definition of a language given the regular expression

texts:
Consider the language:
$$
L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\}
$$

I know that there is a DFA that accepts this language, and furthermore, that the regular expression is:
$$
(0 \cup 10)^* 1^*
$$

I'm asked to obtain a formal recursive definition of $L_1$, that is, find a basis $B \subset \Sigma^*$ and a finite set of functions on strings $\mathcal{F}$ such that $L_1$ is the closure of $B$ under $\mathcal{F}$, i.e. $L_1 = \langle B \rangle_{\mathcal{F}}$

I'm not sure how to go about this. Every way I can think to "encode" the regular expression into "functions" that build the language they're really ugly or involve piecewise definitions (if $x$ doesn't end with 1, otherwise, etc.)

Is there a simple and clean way to do this?


texts: Find optimal alignment between 2 strings with gap cost function

texts:
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
Given two strings S1 and S2, find the score of their optimal global alignment with gaps.
The gap costs are given by a general function-(). It is known that for gaps lengths- ≥ , () equals a constant C.
Suggest an algorithm solving the problem with space O(min{|S1|,|S2|}*d) and time O(|S1|*|S2|*d).
Instruction: When choosing the optimal gap length at each matrix entry, process separately the gaps
of a length less than d and the longer gaps. Store in each matrix entry the optimal value obtained by
using the longer gaps, in addition to the regular optimal value.
Now we learned the following 2 algorithms:
Alignment with gaps where we do not know anything about the cost function:

Alignment with affine gap cost function

my solution:
I know that I have to use a d-rows table in order to meet the space requirements,
and to use both methods but I'm having troubles to combine it into one recursive formula,
Here is what I have done so far:

But I'm not sure how to include the cost for elongating an existing gap that is longer than d, and not even sure how to check if my recursive formula is correct.
Any help would be appreciated!


texts: is any faster algorithm to calculate this series? ∑∑ai/aj

texts:
I am wondering if it is possible to calculate the following double sum, where $a_1,\ldots,a_n$ are positive integers, in time faster than the trivial $O(n^2)$:
$$
\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{a_i}{a_j} \right\rfloor.
$$
For example, if $a_1 = 1, a_2 = 2, a_3 = 3$ then the sum is $9$.


texts: How to distinguish between the different frequency domains?

texts:
Sometimes the terms 'Fourier domain', 'complex frequency domain', 'Frequency domain' and 's domain' are used interchangeably. Take these answers here for example.

Can you really use them interchangeably all the time, without being technically wrong? So, could you describe what would be wrong if I would replace 's domain' by 'fourier domain' for example? Or replacing 'complex frequency domain' by 'frequency domain'?


texts: Bipartite graph matching with multiplicities

texts:
Let's say we have N people, each of them holds several colored cards (for each color and person pair the number cards held is no more than one). We want algorithm determine how to take exactly one card from each person (denote this set of taken cards S), so the following function would be maximal: number of colors satisfying condition - there is at least k cards of this color in S.

In case of k=1 it's well-known problem of maximal matching in bipartite graph.

In case of k>1 this "matching" must have vertices of degree k on on side of bipartite graph. (It can be reformulated as a problem of finding maximal disjunct covering subset of specific set of coverings (in general case i think it's NP-complete?).

Does anyone know if this problem for k>1 NP-complete or can be solved in polynomial time (specifically for k=2)?


texts:
The Problem: A CPU produces the following sequence of read addresses in hex.  Suppose the cache is empty to begin with and assuming an LRU replacement, determine whether each address produces a hit or miss for fully associative cache

20 0010 0000
04 0000 0100
28 0010 1000
4C 0100 1100

Here is the format that we use for the address

I am not quite sure what the addr field is for but I am assuming its the actual address in RAM.(Please correct me if this is wrong)

I know that it can't be apart of the TAG because the TAG portion is made up of bits and C in one of the example addresses above is not a bit(it's a hex digit)

Here is the table I made thus far to store my results.

The red entry I highlighted was the entry I am not sure about. I know that with 3 index bits, the cache will have 8 cache lines. When the CPU goes to the cache for the third address, will it be a hit because the tag already exists(1st cache line) and not add that data or will be a miss and the data will be added because the cache isn't full yet?


texts: Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $

texts:
I'm trying to find a CFG for the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
What I thought about unsuccessfully is the following:
$S \rightarrow SASBS \mid SBSAS \mid \epsilon$
$A \rightarrow a \mid aa \mid aaa $
$B \rightarrow b \mid bb \mid bbb $
Which has the following problems:
(1) It does not take into account words that do not have a's or b's
(2)
It is possible to add a greater number of a's or b's than the allowed distance, for example aaabaaab is a word generated by that CFG
I've been thinking about it for a long time and it seems like a dead end because it seems that making CFG's is more of an art than anything else, I would greatly appreciate any help


texts: How to efficiently represent any possible mutations to a string of a given length?

texts:
I'm trying to find a "language" or a way to express any change that has occurred to a string.

I'm given two strings; a seed string and a new string of the same length that came from it. I'm trying to find the "algorithm" or causes that made the second string what it is.

Now, my current thinking is to come up with a "master list of steps" that I could then experiment with in different combinations in order to determine the correct algorithm to go from the first string to the second. This "master list" is potentially infinite, but I'm hoping to find a subset of steps that, taken in combination could describe any possible change to any possible string.

Below I have an example of a string and and altered string. I've come up with two steps that can be combined in an algorithm that, taken together, explain how it changed. That is to say given the original string, I can reproduce the mutated string by applying both steps to the original string:

Original String

A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q

Mutated String:

A   B   F   D   E   G   H   N   I   J   K   M   C   L   O   P   Q

The first step could be to express simply which indices changed. Something perhaps like this: _ _ X _ _ X X X _ _ _ X X X _ _ _

The second step could be to express which indices will adopt the values of other indices in the string. For example: index 2 adopts index 5's value, index 5 adopts 6, 6 gets 7, 7 gets 13, 13 gets 11, 11 gets 12, and 12 gets 2 for example. That might be expressed by something like this: _ _ 5 _ _ 6 7 (13) _ _ _  (12) 2 (11) _ _ _

The steps above could be done in any order but must both be applied to the seed string. The first step tells us which letter have and have not changed, and the second step tells us what they changed into.

These steps make up an algorithm which is sufficient to describe how this string has changed but can't describe strings that introduce new letters or have other types of changes, thus I'll need more possible types of steps to express different kinds of changes.

Now I suppose this is a type of compression. idk. But is making a myriad of steps, and then combining them in different ways the appropriate way to do this? Or am I barking up the wrong tree here?

It seems intuitive to me that if I'm going to receive many strings like the one above that change in many different ways that I can predict yet then in order to express those changes succinctly I should create a bunch of these types of "steps" that I can put together as needed to create algorithms for expressing such change. Is my intuition correct? What kinds of problems is this related to? I don't know the correct vocabulary to use.


texts:
There is a simple-looking problem.

Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and integer value $x$, find last digit of polynomial value at point $x$, or, equivalently, $p(x) \mod 10$.

My approach was to use Horner's rule for $p(x)$:

$$ c_{0} + c_{1} x + \dots + c_{n - 1} x^{n - 1} = c_{0} + x \left( c_{1} + x \left( c_{2} + x \left( c_{3} + \dots + x \left( c_{n - 2} + x c_{n - 1} \right) \dots \right) \right) \right) ,$$

but for every multiplication we take current value modulo 10. Here is a Python function implementing this algorithm.

def solve(c, x):
    xmod = x % 10
    value = c[-1] % 10
    for i in range(len(c) - 2, -1, -1):
        value = (value * xmod + c[i]) % 10
    return value

Are there better algorithms in sense of computational complexity (i.e. faster)?


texts: Intuitive proof for Floyd's cycle detection algorithm

texts:
I am trying to understand Floyd's cycle detection algorithm. I can see why the algorithm works.

  When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some point in the cycle.

Is there any proof that proves the above point? I mean, without assuming that Hare and Tortoise meet at some point when Hare moves twice the speed of Tortoise and then proving.

In the wiki, I can understand the following paragraph.

  The key insight in the algorithm is that, for any integers $i ≥ μ$ and $k ≥ 0, x_i = x_{i + kλ}$, where λ is the length of the loop to be found and μ is the index of the first element of the cycle

But it is followed by the following point which I could not understand.

  in particular, $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ

How does the author come to conclusion that $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$

Can somebody please help me in understanding this?


texts:
I have a question regard online learning with SGD. Is there a way to give a statistical guarantee that the value obtained after $n$ samples deviates at most $\epsilon$ from the real value?
Thank you guys.


texts: Modeling timing characterists of an architecture

texts:
I am building a system and I have a couple of architectures in mind. I want to have an idea of which architecture is likely to be most performant (quickest).

I can make different decisions like
1) Do everything in one thread
2) Separate this part into one thread, that part into another thread since it can run in parallel and so on

Instead of actually building the system in two different ways and seeing how it performs, is there a way to quickly model/prototype the system where I can express the above concepts and the times it takes for inter thread I/O etc (of which I have a very good estimate) and use the model/prototype to estimate which architecture is better?


texts: algoritm to convert a monoid into an automaton

texts:
In literature, is there an algoritm to convert a monoid into an atomaton?

I am looking for references/applications.


texts: Increase-key and decrease-key in a binary min-heap

texts:
In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally listed for min-heap? I imagine it is possible to do that in O(height) by iteratively swapping the increased element (x) with the minimum of its children, until none of its children is bigger than x.

e.g.

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      {
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }
}

Is the above correct? If not, why? If yes, why isn't increase key listed for min-heap?


texts:
I'm very interested in computing and programming. I have done a lot of programming with different languages although I have a question nobody was able to answer until now.

I question myself how is software related to hardware. to be more specific what are the basic mechanisme which make it possible for hardware to understand software code?

for example : when you put on the computer it starts at a certain point in the register and feeds it into the apu. afther that I'm stuck ....

edited the question


texts: Help understanding main memory to cache block mapping

texts:
I'm currently self-learning on the cache memory and have come
across a method on how to find out which cache block a memory address will be
mapped to:
cache block index = memory address in decimal % no. of cache blocks

However, I have also come across another method that also finds which cache block a memory address maps to by finding its tag, index and block offset. Yet both seems to give different results.
Eg:
Where would memory address 6146 of 32-bits be mapped to in a directly-mapped cache consisting of 1024 4-bytes blocks?
Using the 1st method, I get:
6146 % 1024 = 2

Using the 2nd method, I get:
Let B be the size of a cache block,
b be the block offset,
i be the index,
S be the no. of blocks
and t be the tag bits

b = log₂B
  = log₂4
  = 2

i = log₂S
  = log₂1024
  = 10

t = 32-2-10
  = 20

6146 in binary:
0000 0000 0000 0000 0001|1000 0000 00|10
tag                     |index       |block offset

1000 0000 00 = 512 in decimal

In method 1, I see that memory address 6146 should be mapped to cache block index 2. But in method 2, I see that memory address 6146 should be mapped to cache block index 512 instead. So which method is right? Is memory address 6146 mapped to cache block index 2 or cache block index 512? Am I just mixing up the 2 methods (probably am)? If so, what exactly is each method for (since online says both are for mapping memory address to cache block)?
Much thanks and apologies if my question isn't quite clear in advance! (Learning cache has been rather confusing for me )
EDIT: The only possible reason I can think of is that the 1st method is only applicable if the cache block size is 1 byte, which would make
b = log₂1
  = 0

t = 32 - 0 - 10
  = 22

6146 in binary:
0000 0000 0000 0000 000110|00 0000 0010
tag                       |index

in method 2, giving us cache block index 2.
I'm not sure if this is the right reasoning however.


texts: Useful functions between polylogarithmic and polynomial?

texts:
I'm wondering if there are any useful functions asymptotically greater than a polylogarithmic function and less than a polynomial function.

That is, a function $f(n)$ such that

$f(n) = \omega(\log(n)^k)$  for some constant $k > 0$

and

$f(n) = o(n^k)$ for some constant $k > 0$

What I mean by useful, is that it was used in a proof, algorithm, etc. rather than simply producing a function to fit these restrictions.


texts: Running time of heap sort, when all number are identical

texts:
Given n numbers that all are identical, then what would be the running time of heap sort?
Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?


texts: Error solving the next recurrence: $T(n)=7T(n/2)+n^2$

texts:
Hello I'm trying to solve this recurrence with the method that says the teacher that when you get to
\begin{align*}
T\bigg(\frac{n}{2^{k}} \bigg)
\end{align*} you do
\begin{align*}
\frac{n}{2^{k}} &= 1 \qquad (\text{by definition})\\
k &= \log_{2}(n)
\end{align*}

\begin{align*}
T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &=
7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &=
7^{k}T\bigg(\frac{n}{2^{k}}\bigg) + \sum_{j=1}^{k-1} 7\frac{n}{2^{j}}+n^{2}\\ &=
7^{\log_{2}(n)} + \sum_{j=1}^{\log_{2}(n)-1} 7\bigg(\frac{n}{2^{j}}\bigg)^{2}+n^{2}\\
\end{align*}

After developing, I have left
\begin{align*}
7^{\log_{2}(n)}+n^{2}
\end{align*}
But I know the solution is
\begin{align*}
n^{\log_{2}(7)}
\end{align*}

What am I doing wrong?


texts: Find k compatible objects with minimum total penalty

texts:
Assume we have a set of $n$ objects $X=\{x_1,x_2,\ldots,x_n\}$, where each object $x_i$ has a penalty $p_i$. Additionally, we have a set of incompatibility constraints $C=\{(x_i,x_j),\ldots\}$, where a tuple $(x_i,x_j)$ says that object $x_i$ is incompatible with object $x_j$.  The problem is to find a subset $Y$ of $k<n$ compatible objects that minimize the sum of penalties, i.e. $\min_{Y} \sum_{x_i \in Y} p_i$. The objects in $Y$ need to be compatible, i.e. $\forall x_i,x_j \in Y: (x_i,x_j) \not\in C$.

Let me make an example. Assume we have 4 objects $X=\{x_1,\ldots,x_4\}$ with penalties $p_1 = 2,\ p_2 = 0.1,\ p_3=3,\ p_4=100$. Furthermore the following incompatibilities are given: $C=\{(x_1,x_2),\ (x_2,x_3),\ (x_3,x_4)\}$. The $k=2$ compatible objects that minimize the function are $Y = \{x_1,x_3\}$ with a total penalty of $5$. Object $x_2$ with the least penalty is not part of the solution, because the only compatible object is $x_4$ with a penalty $p_4=100$.

I have two questions:

Is this problem already known under some name or a variation of a known problem?
Is there an efficient (polynomial time) algorithm to solve it?


texts: Proving a LL(1) equivalent grammar doesn't exist

texts:
Consider the following CFG

$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS$

How can we prove formally that an equivalent $LL(1)$ grammar does not exist. I feel that intuitively an equivalent $LL(1)$ grammar doesn't exist, but I'm unable to prove this formally.


texts: Classes of outer totalistic cellular automata

texts: I'm wondering if anyone knows of any place where the Wolfram classifications of many outer totalistic cellular automata have been catalogued. The classes of a few examples are given in A New Kind of Science, famously that of Rule 224 (Life) or more simply ones like Rule 0 which kills all of the cells. I'm wondering if there's any place where these classes have been collected, for a research project. Thanks!


texts: Reduction from 3-Partition problem to Balanced Partition problem

texts:
The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks whether $2n$ integers can be partitioned into two equal cardinality sets such that both sets have the same sum. Both problems are known to be NP-complete. However, 3-Partition is strongly NP-complete. I haven't seen in the literature any reduction from 3-Partition to Balanced Partition.

I'm looking for (simple) reduction from the 3-Partition to the Balanced Partition problem.


texts:
Suppose a simple program is reading messages from a distributed cluster.
The cluster has 3 partitions, and the program has three readers that are assigned one partition each (The setup will always be x partitions connected to x readers, where x can be 3, 4, etc... Each reader handles a specific partition alone. Hence, it only makes sense to have the exactly same number of readers and partitions). The readers work in parallel.
When the cluster receives a messages it puts that message into the partition that is less crowded with messages.

Suppose that all the 3 partitions have the same load of data.

If the total load of data is n messages (in all the partitions), then, because we have 3 readers it is possible to divide the reading process in n/3 parts.
This intuitively states that: The capacity of reading increases linearly with the number of added partitions and readers.

The more readers and partitions we have, the faster it will be. It is clear for me, and this is quite simple, but I am not able to find a mathematical proof for this.

What would be the simplest mathematical proof for this scenario?