texts: How to specify mutated types mathematically?

texts:
Say I have an object which I pass to a method, and the method returns that same object, just mutated.
So it goes like this:
doSomething({ a: 1 })
// { b: '1' }

function doSomething(input) {
  input.b = String(input.a)
  delete input.a
  return input
}

How do you specify a type for this object and type for the action properly in detail? Not necessarily using any particular language or framework or tool, but generically, mathematically? What should happen here? I understand this is why you introduce immutability and pure functions. That would make it easier, so you start with one thing, leave it unchanged, and then receive a completely new object, which starts as output in an "unchanged" state sort of.
But without resorting to this immutability and pure-function state, how would you mathematically specify the types and the "transformation" (function) in this case?
type DoSomethingInput {
  a: Int
}

type DoSomethingOutput {
  b: String
}

This is partially true. However, it doesn't take into account the fact that the DoSomethingInput object is no longer of that type! It got mutated in the process. So part of me just wants to do this:
type DoSomethingObject {
  a?: Int
  b?: String
}

Then at the start, the optional a is present but b is absent, and at the end a is absent and b is present.
But imagine we had a way more complex deeply nested object structure to start with, and then we mutate that object in extremely complicated ways. Too much to try to write an example of this, so just imagine that. Then we would probably have a type DoSomethingObject with almost every of 100 deeply nested properties all optional, which would start to not make sense. Perhaps there are 5 or 10 intermediate "clearly distinguishable" substates of this object while it's being transformed. Then it would make more sense to organize the type differently. But in the end, still, it is being mutated in crazy ways... So how do you say "this type starts as x and ends as y"?
That is, to put it in a different way, we start with DoSomethingInput, and that is replaced physically by DoSomethingOutput I guess. After the action/function/transformation, there no longer exists an object of type DoSomethingInput, that object is now of type DoSomethingOutput. It's as if like this:
globalWorldState = [ { a: 1 } ]
actionApplied(globalWorldState) // doSomething
globalWorldState = [ { b: '1' } ]
where globalWorldState[0] = globalWorldState[0]'

But even something like that doesn't make sense, it doesn't capture it. You would have to say more like:
where globalWorldState[0] = globalWorldState[0]'
  yet added b: String(a)
  and then removed a

Basically I'm wondering how to do I conceptualize this and capture it in type definitions, in a mathematically general way? I would like to say that some input object to an action becomes the output after being mutated, and so the original typed input is gone and it's now of a new type. How could that be stated mathematically?


texts: Prove whether this problem is decidable or undecidable

texts:
So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state.

I convinced myself that this problem is decidable, but I am having trouble proving so. A rough outline of my answer would be : Assume we have a TM T that has only one halting state, and if it wants to go through all the states it needs to pass through this halt state and we somehow need to show how they cycle through all the states as such.

Any help would be beneficial, thanks!


texts: What makes a pseudorandom generator, a high quality one?

texts:
Reading this answer to this SO question: Why do we not combine random number generators?, it talks about

  very high-quality PRNG (Pseudo Random Number Generator)

so it makes me wonder what constitutes a high-quality PRNG, I assume you can sum it up as it being "more random", but

Question1: Which qualities of a PRNG are used to describe how 'random' or 'good' it is?
Question2: If you have a 'bad quality' PRNG, is there a way to make it better quality?


texts: How to Prove NP-Completeness of Minimum Crossing Problem?

texts:
In graph theory, the crossing number cr(G) of a graph G is the lowest
  number of edge crossings of a plane drawing of the graph G.
  (from wikipedia)

I know that the problem of counting the Crossing Number of a graph to be less than or equal to K is proven to be NP-Complete by Garey and Johnson in 1983. I couldn't find the actual proof papers though.

So, what is the proof idea?

One way would be to reduce (in polynomial time) from some known NPC problem but to which one?


texts:
Consider the following algorithm:

run algorithm A until a solution or out of memory
run algorithm B

Then if A does not solve the problem, a computer with less memory has an advantage.

This could be solved by running A and B in parallel, but then the resulting parallel algorithm could be renamed A' and run:

run algorithm A' until a solution or out of memory
run algorithm B'

for some algorithm B', possibly producing a similar result (out of memroy is an advantage).

Also, more generally, if an algorithm goes in a wrong direction, a weaker computer has an advantage.

My questions:

Could you describe systematically such cases when weaker computers have advantage?
Could you refer to some articles or books (preferrably open access) on this topic?
What's about a generic solution of this "trouble"?


texts: Trouble understanding this dynamic programming solution

texts:
Here is the question:

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.

for example: If n=3 and k=1

and the given tree is    1---2---3

Then the total valid subtrees would be 6

{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}

I know I can enumerate all 2^n trees and chack the valid ones, but is there some approach that is faster? Can I achieve polynomial time in n? Something close to O(n^3) or even O(n^4) would be nice.

for k=1 this value turns out to be 2*n

There was a solution provided for this one as:

This is a fairly typical instance of the DP-on-a-tree paradigm. Let's generalize the problem slightly by allowing the specification of a root vertex v and stratifying the counts of the small-boundary trees in two ways: whether v is included, and how many edges comprise the boundary.

The base case is easy. There are no edges and thus two subtrees: one includes v, the other excludes v, and both have no boundary edges. Otherwise, let e = {v, w} be an edge incident to v. The instance looks like this.

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

Compute recursively the stratified counts for L rooted at v and R rooted at w.

Subtrees that include v consist of a subtree in L that includes v, plus optionally e and a subtree in R that includes w. Subtrees that don't include v consist of either a subtree in L that doesn't include v, or a subtree in R (double counting the empty tree). This means we can obtain the stratified counts by convolving the stratified counts for L with the stratified counts for R.

Here's how this works on your example. Let's choose root 1.

  e
1---2---3

We choose e as shown and recurse.

1

The vector for includes-1 is [1], since the one subtree is {1}, with no boundary. The vector for excludes-1 is [1], since the one subtree is {}, also with no boundary.

2---3

We compute 2 and 3 as we did for 1. The vector for includes-2 is [1, 1], since {2, 3} has no boundary edges, and {2} has one. We obtained this vector by adding the includes-2 vector for 2, shifted by one because of the new boundary edge to make [0, 1], to the convolution of the includes-2 vector for 2 with the includes-3 vector for 3, which is [1, 0]. The vector for excludes-2 is [1] + [1, 1] - [1] = [1, 1], where [1, 1] is the sum of the shifted includes-3 vector and the excludes-3 vector, and the subtraction is to compensate for double-counting {}.

Now, for the original invocation, to get the includes-1 vector, we add [0, 1], the includes-1 vector for 1 shifted by one, to the convolution of [1] with [1, 1], obtaining [1, 2]. To check: {1, 2, 3} has no boundary, and {1} and {1, 2} have one boundary edge. The excludes-1 vector is [1] + [1, 2, 1] - [1] = [1, 2, 1]. To check: {} has no boundary, {2, 3} and {3} have one boundary edge, and {2} has two boundary edges.

I am unable to understand this fully. Can anyone help?


texts: Fastest in-place sorting algorithm for Epochtime

texts:
I need to sort a lot of rows (from 1GB to 3GB) by EpochTime (a single value of every row).

What is the fastest in-place sorting algorithm for this task?  Radix Sort?

I would like the fastest sorting algorithm but I think that I could fail on limit of memory so I would prefer an in-place algorithm.

EpochTime should be unique (I didn't check).  The Max and Min values are about a range of 4 hours, so they're pretty similar.

I'm asking this because I think there could be some optimization for some sorting alghoritms, also because epochtimes are pretty much known. I checked for Counting Sort (after all I'm talking about integers), but didnt' look like best case.


texts: The transfer of control is often completed through some type of software interrupt instruction. These special instructions result in the CPU to save the current state of the machine and transfer control to a function in the operating system. They are like a cross between an ordinary subroutine call instruction and a hardware interrupt. My question is that Why are special instructions used to implement system calls? Why not use normal subroutine calling instructions?


texts: Why not use large $k$ in a $k$-ary tree?

texts:
Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case.

To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, splay trees, etc.

If we use a $k$-ary tree, we can get $O(\log_k n)$ searches, inserts, and deletes in best case. Similarly we can "maximize" the occurrences by using self-balancing trees.

I know these are asymptotically of the same order, i.e. $O(\log n)$, but the constant could be huge in practice.

The huge reason I can think of is that by using larger $k$'s, you lose the ability to make a decision based on one comparison.

What are other reasons larger $k$ $k$-ary trees aren't used in practice?


texts: Converting a NFA to its equivalent regular expression

texts:
I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions.

I have the following NFA:

I'm using the state elimination method to obtain the regular expression for the NFA. So I first introduced two new states, $q_{start}$ (the new start state of the NFA) and $q_{end}$ (the new and only accepting state of the NFA).
After that, I eliminated the states one after the other.

To eliminate the states, I pick a state $p_e$ to be eliminated. Then for every pair $(p_1,p_2)$ with $p_1, p_2 \neq p_e$ and transitions from $p_1$ to $p_e$ and from $p_e$ to $p_2$, I determine the labels $r_0,r_1,r_2,r_3$ of this general automaton

wipe out $p_e$ and replace $(p_1,r_0,p_2)$ with $(p_1,r_0+r_1 r^{*}_2r_3,p_2)$.

I already eliminated states $q_0$ and $q_1$, but I have no idea how to eliminate state $q_4$, since it has no outgoing transitions except to itself. Could you please help me out with that?


texts: What is the growth rate of the world wide web?

texts: Is there any way to estimate how much data is added to the world wide web each second? Are there any studies about this?


texts:
I apologise if this is not the right place for this question... I didn't want to ask on Stackoverflow or CodeReview as it will closed in minutes as "too broad".

A client of mine is writing an API that takes a piece of personal-identifying information as the parameter in the URL, and has asked that the value is hashed using SHA512.

Normally when I deal with anything that involves personal information in this way, I'd encrypt it using a shared private key... but I'm really fuzzy on the whole idea of hashing.

My understanding of hashing was effectively...

take the input value and create a hash from it
when checking the value, create a hash from the new input value and compare them

What I'm struggling to understand (and I don't want to ask the client and show my ignorance) is how does the client take the hashed value and turn it back into the original input value?

And in particular, if the client can convert the hash back to the original input, what is stopping anybody else doing it?

And if other people can convert it back, what's the point in hashing it in the first place?

Update

After speak to the client, the answer (as many of you guessed) is that they are storing the hash of the PII in their database, and doing a match-search against the value I will be sending through.


texts: Comparing wait-signal alternatives for synchronizing two piece of programs

texts:
I came across following problem:

  A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i]=g(a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.

+-------------------------+-------------------------+
| Process X:              | Process Y:              |
| private i;              | private i;              |
| for (i=0; i < n; i++) { | for (i=0; i < n; i++) { |
|    a[i] = f(i);         |    EntryY(R, S);        |
|    ExitX(R, S);         |    b[i]=g(a[i]);        |
| }                       | }                       |
+-------------------------+-------------------------+

  How to correctly implement ExitX() and EntryY()?

Given solution:

+---------------+----------------+
| ExitX(R, S) { | EntryY(R, S) { |
|   wait(S);    |   signal(S);   |
|   signal(R);  |   wait(R);     |
| }             | }              |
+---------------+----------------+

Question 1 - can we swap wait and signal operations?

My doubt is will it make difference if we swap these operations, something like below?

+---------------+----------------+
| ExitX(R, S) { | EntryY(R, S) { |
|   signal(R);  |   wait(R);     |
|   wait(S);    |   signal(S);   |
| }             | }              |
+---------------+----------------+

I believe there is no difference in the behavior and overall outcome of the code when either of above two solutions is used. Am I right?

Question 2 - is weak alternation even required for this problem?

I feel the solution above does enforce weak alternation between two processes. That is, at max process X can generate k+2 a's when Y has generated k b's. To produce (k+3)th a, X has to wait for Y to produce (k+1)th b, as during computation of (k+1)th b, Y will signal X, unblocking it. Such weak alternation is not required.

Also I feel we dont really need two semaphores here and one semaphore T will suffice. It will be used by X to signal Y when it is blocked, in case there are no further a's produced by X, which can be used by Y to produce b's. Also this will need us to have a variable m share by both processes to keep track of difference between a's and b's produced by X and Y as follows:

+-------------------------+-------------------------+
| Process X:              | Process Y:              |
| private i;              | private i;              |
| for (i=0; i < n; i++) { | for (i=0; i < n; i++) { |
|    a[i] = f(i);         |    if(m==0) wait(T);    |
|    m++;                 |    b[i]=g(a[i]);        |
|    if(m==1) signal(T);  |    m--;                 |
| }                       | }                       |
+-------------------------+-------------------------+

Question 3

The text from which I was reading this says having signal() in both EntryY() and ExitX() as a first statement will cause process X to do two signal(R) operation without a wait(R) being done in between by process Y. In given solution, wait() is done twice by process X without letting process Y to do signal() multiple times in between. I believe both have same overall effect of weak alternation as explained in question 2 and none is more preferable than other. Am I correct with this?


texts: Matrix Chain Multiplication Greedy Approach

texts:
In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic Programming but I have found a greedy approach to this problem.

For example a chain of Matrices of the size of:

   A        B       C       D
40 * 20  20 * 30 30 * 10 10 * 30

First list all of the possible consecutive pairs, and the 2 different dimensions of the pair:

        X
AB:  40 * 30
BC:  20 * 10 <----
CD:  30 * 30

Then multiply the pair that has the lowest product in the X column and the list will turn into:

   A       BC      D
40 * 20 20 * 10 10 * 30

Repeat the first 2 steps until all of the matrices are multiplied together:

          X
A(BC): 40 * 10 <----
(BC)D: 20 * 30

  ABC      D
40 * 10 10 * 30

             X
(A(BC))D: 40 * 30 <----

This have a time complexity of $O(2n^2 + 2n\log n)$.

I have tested a Java implementation on smaller test cases and it runs fine.

Does this method work, or is there a something I have overlooked?


texts:
The Triangle Cover Graph problem is this:

  Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also contains a vertex of the set?

This problem is obviously in $NP$ as its verifier is just the set which you can easily check.  However, what's the reduction to be able to show that this is NP Complete?

I recognize the fact that a good reduction for this problem would be for 3-SAT as you could easily take a 3-sat instance and make a 3-vertex triangle in the graph corresponding to the variables which are in each clause.  However, I wasn't able to come up with a way to connect the different triangles together to ensure that the assignment of vertices would be a satisfiable truth assignment.


texts: Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive?

texts:
Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$.

How do I show that each $L_i$ are recursive ?

I see that for $x \in \Sigma^*$, $x$ belongs to exactly one $L_i$.

My idea is to run every Turing machine simultaneosly, stopping as soon as one of them accepts $x$ (must happen at some definite time by assumption).

What theory can I use to make my idea rigorous ? I've considered an non-deterministic TM, but also a $k$-tape TM, but none seems to suit my needs ?

Can someone help ?


texts:
in Programming language course my professor take an example.

Suppose the following code:

int x=initialization();
Thread T1=new computethread(x);
Thread t2=new evaluatethread(x);
...
...
Thread t100=new evaluatethread(x);

threads t1 to t100 needs the initial value of variable x for their computation and t1 need to change the x, which transfer of parameter for computethread, evaluatethread is preferred?

my professor say:

1) call by value result

2) call by ref

is preferred for sending x to computethread,  evaluatethread, why call by result or call by name or this order like   2) call by value result,     1) call by ref is not preferred?
why he conclude these are better?


texts: Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with a LL(∞) grammar, which type of ambiguities can't be solved?


texts: What is the regular expression to the given language?

texts:
I can't really find out, how can the following given Language be written down with regular expressions

$
L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \}
$

I had some guesses, but I don't know how to express the part $a^{3k-1}$ of the Language.
Probably it should look something like this:

$(aaa)^+$ [something] $b^*(aa^+)$


texts: Quicksort where element comparison outcome is random. Probability of element being in a certain position

texts:
So we have this block of pseudocode:

Monsters = [M1,M2,M3,M4,M5,M6,M7,M8];
qsort(Monsters,rand_compare);

  qsort() sorts the array via quicksort where we use the last element
  as pivot. To compare two elements it uses rand_compare, which, with
  equal probability (i.e., 1/2 either way), will return either "1. element is bigger" or
  "2. element is bigger" and never "both are equal". What is the
  probability that M8 appears in position 0, 1 or 2, respectively, after
  applying qsort ?

I'm really not sure how to tackle this question. Intuitively it should be 1/8 for every position. Does it depend on what implementation of quicksort you use?


texts: Maximizing total value given bound on total cost

texts:
I have a list of pairs with values and costs:

    | value | cost |
    11, 1000
    7, 700
    7, 700
    6, 700
    2, 400
    2, 500
    1, 600

The list is ordered by value/cost decreasingly.
The task is, given a budget X find the maximum value you can get while keeping the total cost within the budget.
In the sample example, if X=1400, the maximum value would be 14.

What algorithm would be the most efficient to find this value?


texts: Efficiently computing or approximating the VC-dimension of a neural network

texts:
My goal is to solve the following problem, which I have described by its input and output:
Input:
A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$).
Output:
The VC-dimension (or an approximation of it) for the neural network with topology $G$.
More specifics:

Each node in $G$ is a sigmoid neuron. The topology is fixed, but the weights on the edges can be varied by the learning algorithm.
The learning algorithm is fixed (say backward-propagation).
The $n$ source nodes are the input neurons and can only take strings from $\{-1,1\}^n$ as input.
The sink node is the output unit. It outputs a real value from $[-1,1]$ that we round up to $1$ or down to $-1$ if it is more than a certain fixed threshold $\delta$ away from $0$.

The naive approach is simply to try to break more and more points, by attempting to train the network on them. However, this sort of simulation approach is not efficient.

Question
Is there an efficient way (i.e. in $\mathsf{P}$ when changed to the decision-problem: is VC-dimension less than input parameter $k$?) to compute this function? If not, are there hardness results?
Is there a works-well-in-practice way to compute or approximate this function? If it is an approximation, are there any guarantees on its accuracy?
Notes
I asked a similar question on stats.SE but it generated no interest.


texts: Sequence prediction with known information

texts:
recently Hamas has shot a lot of rockets to Israeli cities. I found a large database containing thousands of entries from the past 3 days.
The database is a large list of triplets in the form of $(time, date, area)$. Ultimately, I would like to predict the "new elements" in this list - the times at which Hamas is more likely to shoot rockets (and where to).
From the data we can easily see a few characteristics: the rockets are sent in batches to nearby cities. Also a really large portion of cities who where shot are closer to the place where the rockets are shot from.
So my question is: How can I construct a machine learning model that is capable of predicting the next time and area of missile shootings, using this dataset and the prior knowledge I have?


texts: Partition graph in a way that minimizes inter-partition edges

texts:
I have a graph in which certain vertices are labeled. I need to assign labels to all of the other vertices in a way that minimizes the number of edges between different-label vertices.
How can I do this efficiently?


texts: Can PRNGs be used to magically compress stuff?

texts:
This idea occurred to me as a kid learning to program and
on first encountering PRNG's. I still don't know how realistic
it is, but now there's stack exchange.

Here's a 14 year-old's scheme for an amazing compression algorithm:

Take a PRNG and seed it with seed s to get a long sequence
of pseudo-random bytes. To transmit that sequence to another party,
you need  only communicate a description of the PRNG, the appropriate seed
and the length of the message. For a long enough sequence, that
description would be much shorter then the sequence itself.

Now suppose I could invert the process. Given enough time and
computational resources, I could do a brute-force search and find
a seed (and PRNG, or in other words: a program) that produces my
desired sequence (Let's say an amusing photo of cats being mischievous).

PRNGs repeat after a large enough number of bits have been generated,
but compared to "typical" cycles my message is quite short so this
dosn't seem like much of a problem.

Voila, an effective (if rube-Goldbergian) way to compress data.

So, assuming:

The sequence I wish to compress is finite and known in advance.
I'm not short on cash or time (Just as long as a finite amount
of both is required)

I'd like to know:

Is there a fundamental flaw in the reasoning behind the scheme?
What's the standard way to analyse these sorts of thought experiments?

Summary

It's often the case that good answers make clear not only the answer,
but what it is that I was really asking. Thanks for everyone's patience
and detailed answers.

Here's my nth attempt at a summary of the answers:

The PRNG/seed angle doesn't contribute anything, it's no more
than a program that produces the desired sequence as output.
The pigeonhole principle: There are many more messages of
length > k than there are (message generating) programs of
length <= k. So some sequences simply cannot be the output of a
program shorter than the message.
It's worth mentioning that the interpreter of the program
(message) is necessarily fixed in advance. And it's design
determines the (small) subset of messages which can be generated
when a message of length k is received.

At this point the original PRNG idea is already dead, but there's
at least one last question to settle:

Q: Could I get lucky and find that my long (but finite) message just
happens to be the output of a program of length < k bits?

Strictly speaking, it's not a matter of chance since the
meaning of every possible message (program) must be known
in advance. Either it is the meaning of some message
of < k bits or it isn't.

If I choose a random message of >= k bits randomly (why would I?),
I would in any case have a vanishing probability of being able to send it
using less than k bits, and an almost certainty of not being able
to send it at all using less than k bits.

OTOH, if I choose a specific message of >= k bits from those which
are the output of a program of less than k bits (assuming there is
such a message), then in effect I'm taking advantage of bits already
transmitted to the receiver (the design of the interpreter), which
counts as part of the message transferred.

Finally:

Q: What's all this entropy/kolmogorov complexity business?

Ultimately, both tell us the same thing as the (simpler) pigeonhole
principle tells us about how much we can compress: perhaps
not at all, perhaps some, but certainly not as much as we fancy
(unless we cheat).


texts: 2d cellular automata Wolfram binary codes

texts:
This is a similar question to How 2d cellular automata rules works?
However, the answer there did not provide me what I am looking for. Specifically, I want to be able to render these 2d cellular automata forms: https://www.wolframscience.com/nks/p173--cellular-automata/
I cannot find any reference anywhere that explains how to change between a real number and a growth rule. In 1d, the situation is well documented, such as here: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html but in 2d the exact mapping of bits is nowhere to be found. I'd really like to make a program, so that I can for instance enter the number 465 and it will draw the pattern 465 from the Wolfram book. The other stack exchange answer I linked to above provides a possible binary mapping, however the method given there does not produce the same numbers as in the Wolfram reference. The binary value of 465 is 111010001 which does not help me at all. This particular shape is based on adding a cell when exactly one neighbor is currently occupied, so shouldn't we expect to have 4 1's in a row, one for each of the four neighbors? And to make this even more confusing, the last two digits seem to be swapped from the description given on the Wolfram page itself... It seems clear from the other Stack Overflow answer that there is not just one possible binary mapping but many, however given that there already exists a guide with pictures referenced by rule numbers I would really like to actually be able to use those specific rule numbers. Thanks.


texts: How can we combine badly trained decision trees to a good one?

texts:
I was reading about decision trees and this is what I understood:

We build decision trees by choosing an attribute and building subtrees (which are also decision trees) as children of the node representing that attribute. This means that as we go down, in building a decision tree, the no. of training instances that we use to build a subtree decreases. This is because when we build a subtree, we only have to train it using a subset of the original data consisting of instances which satisfy the conditions on the path towards the root node of the subtree.

Now here's the question: We usually believe that if training data is not enough, the model built is incorrect. This would mean that the subtrees down in a decision tree may not be good models (as they were trained using much less data than its ancestors in the tree) and if they are not, how can they be recursively combined to give a full tree which may give a good model? Where is the fault in my reasoning?


texts: Every state in subset automaton is reachable

texts:
I'm currently trying to prove that following NFA $\mathcal{M}_0 = (Q, \Sigma, \delta_0,0,\{0\})$ (see picture below) has an exponentially larger DFA $\mathcal{M}$ accepting the same language.

$\mathcal{M} = (2^Q,\Sigma,\delta,\{0\},F)$ is constructed using the subset/powerset algorithm and I'd like to show that $\mathcal{M}$ is minimal (i.e. $F = \{q \in 2^Q \mid 0 \in q\}$).

My problem is to show that every state $q \in 2^Q$ is reachable. I'm trying to prove this by induction over $|q|$.

It is clear for $|q| = 0$ since $\delta(\{0\},b) = \emptyset$.
For $|q| = 1$ it follows directly from the NFA: $\Delta(\{0\},a^i) = \{i\}$ for $1 \leq i \leq n-2$.

The problem starts in the inductive step. Let $q = \{i_1,\dots,i_k\}$ with $0 \leq i_1 < i_2 < \cdots < i_k \leq n-2$.

For states with $i_1 = 0, i_k=n-2$ (using the induction hypothesis) or $i_1 = 0, i_2=1$ (using the first case mentioned) it is easy to show but in other cases I have no clue how to do it.

EDIT: Beware that the dotted states also have a $b$ loop to themselves (!), i.e. $\delta_0(i,b)=\{0,i\}$ for $1 \leq i \leq n-3$.


texts:
The English Wikipedia article about Turing machine opens with:

  A Turing machine is a mathematical model of computation that defines
  an abstract machine,[1]

As a Hebrew speaker, I read a similar explanation in Hebrew Wikipedia:

  מכונת טיורינג היא מודל חישובי מתמטי אשר
  באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

My problem

I understand this term as reflecting a scientific theory in CS or Math, but interestingly, none of the two opening sentences presented this concept as a scientific theory in either CS or Math.

By scientific theory I meant:

  An idea or set of ideas that can be falsified by principle
  (falsifiability as a condition for it to be real) and that one or more
  reinforcements can make it somewhat more plausible in reality.

But;

If it's a theory in Math, maybe my approach is wrong, because, as far as I understand, in Math the paradigm is different so something is either true or false (i.e, not true).

My question

Is Turing machine a scientific theory in CS?

Update

In comment section, Yuval Filmus said (minor paraphrase):

  Turing machines are a mathematical abstraction.
  They're neither a scientific theory nor a practical engineering idea;
  Actual computers are much better modeled using a different abstraction → RAM machines;
  The relevant scientific theory is the Church-Turing thesis.

This made me wonder "what is the difference between a mathematical model and a mathematical abstraction and does the former or the latter or both, can be based in a "scientific theory"?

This isn't the main question, but you are welcome to explain this in an answer as I think it's relevant.


texts: turing machine for the language L ={w#w' where w<w'}

texts:
I'm blocked with a question for a long time.

L ={X=w#w' where w < w' and w,w' in {0,1}* }

So i'm trying to find :

1-a deterministric turing maching for the language L.

2-a non deterministic for L.

example :

      w=01 w'=111 --> X in L.

      w=1 w'=011 -->  X is **not** in L.

For the deteministic machine , i have an idea only when |w|=|w'|, it's only comparing an alphabet in the first word with an alphabet in the second word.

but i don't know how to solve it when we have two different length ; like my second example .

Do you have any idea for the turing machine?

Thank you.


texts:
I am an undergraduate student in Computer Engineering and going through one of the textbook examples, I am asked to prove that

$T(n)$ is $O(\log{}n)$

Where $T(n)= 5\log_{2} 2n +7$.
I understand that this means that I must prove that $5\log_{2} 2n +7 \leq\lambda log(n)$

For some in n in a neighborhood of infinity. How exactly would I proceed with this?


texts: Why does $\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) = \theta(n\lg(n))$?

texts:
I'm reading a proof on the time complexity of MergeSort which makes this statement without any justification. I've tried to show it myself but I'm not getting far; these are my steps so far.

$\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) =\theta(n\sum\limits_{i=0}^{\lg(n)-1}\frac{1}{2^i})$

Now $\sum\limits_{i=0}^{\infty}\frac{1}{2^i} = 2$, so $\sum\limits_{i=0}^{\lg(n)-1}\frac{1}{2^i} \leq 2$. This means that $\theta(n\sum\limits_{i=0}^{\lg(n)-1}\frac{1}{2^i}) = \theta(2n) = \theta(n)$, but surely not. Where is my logic wrong?


texts: Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?

texts:
I've been given the following problem:

Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:

$\text{Insert}(x)$ – add $x$ to $S$
$\text{Extract_min}()$ – remove the minimal element in $S$ and return it

We can implement with a heap the above methods in $O(\log n)$, however, we're looking at
a bigger picture, a general case that we have no guarantee that $M$ is indeed a heap. Prove that
no matter what kind of data structure $M$ is, that at least one of the methods that $M$ supports must take $\Omega(\log n )$.

My solution:

Each sorting algorithm that is based on comparisons must take at the worst case at least $\Omega(n\log n)$ – we'll prove that using a decision tree: if we look at any given algorithm that is based on comparisons, as a binary tree where each vertex is a compare-method between 2 elements:

if the first is bigger than the second element – we'll go to the left child
if the second is bigger than the first element – we'll go to the right child

At the end, we'll have $n!$ leaves that are the options for sorting the elements.

The height of the tree is $h$, then:

$$2^h \ge n! \quad\Longrightarrow\quad \log(2^h) >= \log(n!) \quad\Longrightarrow\quad h \ge \log(n!) \quad\Longrightarrow\quad h = \Omega(n \log n)$$

Then, if we have a $\Omega(n \log n)$ worst case for $n$ elements, then we have a $\Omega(\log n)$ for a single element.

I'm not sure regarding this solution, so I'd appreciate for corrections or anything else
you can come up with.


texts: Want to know the time complexity inner for loop which is partially iterating the array

texts:
Question: Find out next increasing value of each element in this below array.

int[] array = { 5, 2, 7, 10, 4, 12}

e.g)
     5's nextIncreasingValue: 7
     2's nextIncreasingValue: 7
     7's nextIncreasingValue: 10
     ...
     12's nextIncreasingValue: -1

Implementation:

for(int i = 0; i < array.length; i++) {
        int nextIncreasingValue = -1;
    for (int j = i + 1; j < array.length; j++) {
        if(array[j] > array[i]) {
            nextIncreasingValue  = array[j];
            break;
        }
    }
    PRINT("For " + i + "th next increasing value is: " + j)
}

Now I want to know the time complexity of this program, since each time inner for loop is skipping some of the elements on iteration. So it cannot be O(n^2) even in the worst case.

Kindly explain me what will be the time complexity?

O(n) Solution using stack:

Stack s = new Stack();
for(int i = 0; i < array.length; i++) {
   while(!s.isEmpty() && array[i] > s.peek()) {
         PRINT  s.pop() NIV is array[i];
   }
   s.push(array[i]);
}
while(!s.isEmpty())
   PRINT  s.pop() NIV is -1;


texts: Flow graph with non zero lower bound or 0 capacity

texts:
I am afraid the question title might not be sufficiently accurate but I could not come up with something more accurate
Here is the problem
Given 'n' machines

Each machine has a set of capabilities
Each machine has max availability (A(m))

Given 'm' tasks

Each task requires a set of capabilities
Each task takes a certain time (D(t))
A task has to be performed on one machine only

The problem is to determine whether all tasks can be completed.
I get stuck with the 'one machine only' requirement. The only flow graphs I can come up with do not guarantee a task is not linked to more than one machine.
It's sort of a bipartite matching problem but with capacities > 1
I also ran into XOR-like behavior in flow networks which is similar but has the 'xor' requirement on the 'source' end where I would need it on the target end.
Would anyone have any tips? Is it at all possible to model this as a flow graph?
Tx!
Peter
PS Trying to clarify requirements with more concrete example
Assume digital print systems and print jobs

Each digital press can run for a number of hours
Each press has some finishing possibilities: e.g. 'sheet cutter', 'laminate', 'laser cutter', 'page folding', ....
Each print job requires a number of hours
Each print job needs one or more of the finishing possibilities

Given a set of machines, the availability for each and the finishing possibilities and also a set of print jobs (duration, finishing options needed) determine whether all print jobs can finish
So e.g.

Printer p1 is available for a duration of 10 hours and has features f1 and f2
Printer p2 is available for a duration of 10 hours and has features f2 and f3
Job1, requiring features f1 and f2 takes 8 hours to run
Job2, requiring features f2 and f3 takes 8 hours to run
Job3, requiring feature f2 requires 4 hours to run

A printer that is available for e.g. 10 hours can run 10 x 1 hour jobs or 5 x 2 hour jobs, or 1 x 8 hr job and 1 x 2 hr job, ... Jobs always have to run on a single printer
The flow diagrams I could come up with always result in cases where
8 hours of p1 is assigned to job1 (leaving 2 hours for printer p1)
8 hours of p2 is assigned to job2 (leaving 2 hours for printer p2)
(so far so good)
but then
The 2 hours of p1 and p2 left are used to flow to job3 and the max flow seems to indicate the three jobs can be run (which is not ok)


texts: Partitioning a graph with specific constraints

texts:
We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills these constraints:

|V1| - |V2| = 0 or 1 (V1 and V2 have the same amount of nodes or V1 contains one node more that V2)
either

[case A] all nodes in V1 have edges to all nodes in V2
[case B] all nodes in V1 have no edges to any node in V2

We had a few ideas to find those partitions via divide-and-conquer involving the degrees of each node to differentiate between case A and B. If we find any node v with degree(v) < |V2| then there is a partition with case B, otherwise if we find a node v with degree(v) > |V1| then there is a partition that fulfills case A.
However other than that we have been stuck and extendind or other ideas ended in a dead end.

How do we find those partitions? I'd like to not be given the answer but only a pointer to find a easy algorithm for the problem.


texts: Does a collision oracle for the pigeonhole subset sum problem produce solutions?

texts:
I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11):

  Let $\  l(n) = (1-c)n \ $ for $ \ c > 0  \ $ ...

  Given $a_1, a_2, \cdots, a_n \in \{0,1\}^{l(n)}$ and a target sum $T$, we construct an input to the collision finding algorithm as follows:

  Let the collision finding algorithm select a (non-empty) $ s_1 \in \{0,1\}^n $
  compute $T' = \sum_{i \in s_1} a_i$.  Choose a random $j$ such that $j \in s_1$ and define $a_j' = a_j - T' + T$.
  Give the instance $a_1, a_2, \cdots , a_j', \cdots, a_n$ and $s_1$ to the algorithm that finds collisions.  The algorithm attempts to find $s_2$ such that $f_{(a_1, a_2, \cdots, a_j', \cdots, a_n)}(s_2) = T'$.

  If the algorithm returns $s_2$ that collides with $s_1$ and $j \notin s_2$, then $s_2$ is a solution to our original problem, since swapping $a_j$ and $a_j'$ does not affect the sum over $s_2$.

Where the emphasis is mine.

Where $f$ concatenates $\stackrel{\rightarrow}{a}$ with the sum of the $a_i$'s:

$$ f( \stackrel{\rightarrow}{ a } , S) = f_{(a_1, a_2, \cdots, a_n)}(S) = \ \stackrel{\rightarrow}{a}, \sum_{i \in S} a_i \mod 2^{l(n)} $$

(taken from the top of page 3 from the same paper).

For the life of me, I don't understand how $s_2$ is a solution to the original instance.  Can someone elaborate on what they mean?  What am I missing?

The above definition for the subset sum problem is, if I'm not mistaken, just another form of the pigeonhole subset sum problem (i.e. $\sum_j a_j < 2^n -1$ ).  If I read the above right, they are claiming that, given an oracle that finds collisions, they can then construct a solution to the original (pigeonhole) subset sum problem but I do not see how this is done.  Any help would be appreciated.


texts: Data structure with search, insert and delete in amortised time $O(1)$?

texts:
Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

GetElement(k): Return the $k$th element of the list.
InsertAfter(x,y): Insert the new element y into the list immediately after x.
Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y.  InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

InsertAfter(NULL, a) $\implies$ [a]
InsertAfter(NULL, b) $\implies$ [b, a]
InsertAfter(b, c) $\implies$ [b, c, a]
InsertAfter(a, d) $\implies$ [b, c, a, d]
Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should return an error.


texts: Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

texts:
I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P?

The language of any such regular expression would be guaranteed to be finite. I suppose an equivalent question is whether the problem of constructing a minimal regular expression from a known finite language is any easier than minimizing an arbitrary regular expression. It seems like this should be the case.


texts:
Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time.

I have to find an event that conflict with maximum number of other events.

Conflicts means interval overlaps

The idea is as follows: Sort events according to their starting times and then for each event check whether it conflict with other evenets or not. The first step seems to me doable in $\mathcal{O}(n \log n)$ time, but second step i.e. to find the number of events with which it conflicts is seems to $\mathcal{O}(n)$ Can we do it in $\mathcal{O}(\log n)$ time?

Question : Is it possible to do the second step as mentioned above in $\mathcal{O}(\log n)$ time?


texts: Does every Partially Ordered relation and its dual have the same number of topological orderings?

texts: Given the Hasse Diagram of a Partially Ordered Relation, is it the case that both the POSET itself and its dual POSET have the same number of topological orderings? I have tried a few examples, and although it does seem to be the case, I need a formal way of proving the same. So please help me with this.


texts:
my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my image after processing it are shown in green. As you can see I get many more points from the image than just the black ones, due to other structures inside the picture. So I've got a set of points and I know that there are at least three of them that are on a curve which is approximately a line and the approximate distance between the points is also known. I need to find these three points from my set.

The algorithm should be able to detect whether there is such a structure in the picture or there isn't one.


texts: Convert a string consisting of only digits into an integer array such that the elements form a Fibonacci sequence based on the indices

texts:
Given a string that consists of only digits, return an integer array (without shuffling sequence of string characters) such that the array elements form a Fibonacci series based on indices. If such an array can't be formed return a new array with -1 as the only element.

Fibonacci sequence based on indices means that [element at index i] = [element at index i-1]+ [element at index i-2]

Example 1:
Input: "1235"
Output {1,2,3,5}

Example 2:
Input:"11112233"
Output: {11,11,22,33}

Example 3:
Input: "123456579"
Output: {123,456,579}

Example 4:
Input: "135"
Output: {-1}

The algorithm that I could come up with:

Initialize by finding all possible groups of indices [i, j] such that input[1,i), input[i,j) form the first 2 numbers of the desired result. For each such group, do step 2 as mentioned below.
Call a recursive function that uses the index of the first character of the string that is yet to be parsed (k in this case). This function will parse the string till it can either find a number with which it can extend the Fibonacci sequence or not. If it can, recursively call itself by passing the new index and the list of numbers built till now.
Once the recursion reaches the index == input.length, the list of numbers formed till then is the result needed.
If the list.length < 3 return an array of -1.

I need help finding a better/optimal solution.


texts: The equivalence relations cover problem (in graph theory)

texts:
An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two elements are equivalent.

If I have a graph $G$ and graphs $G_1,\dots,G_k$, we say that $G$ is covered by $G_1,\dots,G_k$ if the set of edges of $G$ is equal to the union of the sets of edges of $G_1,\dots,G_k$.  The edge sets of $G_1,\dots,G_k$ do not need to be disjoint.  Note that any undirected graph $G$ can be covered by a finite number of equivalence relations (i.e., disjoint union of cliques graphs).

I have several questions:

What can be said about the minimal number of equivalence relations required to cover a graph $G$?
How can we compute this minimal number?
How can we compute an explicit minimum cover of $G$, i.e., a set of equivalence relations whose size is minimal and which cover $G$?
Does this problem has any applications apart from partition logic (the dual of the logic of subsets)?
Does this problem has a well established name?

Given the various misunderstandings indicated by the comments, here are some pictures to illustrate these concepts. If you have an idea for an easier to understand terminology (instead of "cover", "equivalence relation", "disjoint union of cliques" and "not necessarily disjoint" union of edge sets), feel free to let me know.

Here is a picture of a graph and one equivalence relation covering it:

Here is a picture of a graph and two equivalence relations covering it:

It should be pretty obvious that at least two equivalence relations are required.

Here is a picture of a graph and three equivalence relations covering it:

It's less obvious that at least three equivalence relations are required. Lemma 1.9 from Dual of the Logic of Subsets can be used to show that this is true. The generalization of this lemma to nand operations with more than two inputs was the motivation for this question.


texts: Finding differences and similarities between tree graphs

texts: Are there any known techniques for "diffing" trees, such as phylogenetic trees?


texts: Filling a board with maximum number of fixed size tiles

texts:
You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), while it's not allowed to cover missing tiles. Currently, I solve it using the following greedy algorithm:

for x in N:
  for y in M:
    insert a tile at (x, y) if it possible

    for x1 in N:
      for y1 in M:
        insert a tile at (x1, y1) if it possible

    remove the tile

I'm sure that it's not the right way to approach this problem, but it passes all tests that are interesting to me. There is a somewhat similar problem, but I doubt that I can reuse it in mine settings. I think that it could be solved by backtracking, but I'm stuck at this point.

Example. Orange pieces are missing.


texts: Definition of "idempotence" of a function?

texts:
Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not idempotent. However, it seems controversial whether the return value is required to stay the same. For example, is the below function idempotent?

int foo = 1; // global
int bar() {
    int ret_val = foo;
    foo = 5;
    return ret_val; // 1, 5, 5, 5...
}

Or is there consensus over this?


texts: Integer linear programming formulation of formula in DNF

texts:
I have multiple sets, e.g.,

$$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$

Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables

$$(1 \land 2) \lor (2 \land 3 \land 4) \lor (1 \land 4)$$

Basically, I need to enforce that either $1$ and $2$ are 1s, or $2$ and $3$ and $4$ are ones, or $1$ and $4$ are 1s, but not all of them. Constants can be added as needed, as well as equalities, inequalities, etc. How can I do that?


texts: How create DFA with multiple finished states for lexers?

texts: Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats etc. How do such DFA? Maybe convert many DFA's to one or join DFA's to one NFA and next convert it to DFA?


texts:
As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design an algorithm which is able to solve such a problem.

If we will never get such a black box then why is it important and, in computer science, do they talk about it?


texts: How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

texts:
Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\dots, x_k \in D$ and $y_1, y_2,\dots, y_k \in R$,
$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, \dots, h(x_k) = y_k) = \frac{1}{|R|^k}$$
The Wikipedia article on k-wise independent hash functions (which uses the above definition) claims that the definition is equivalent to the following two conditions:
(i) For all $x \in D$, $h(x)$ is uniformly distributed in $R$ given that $h$ is randomly chosen from $H$.
(ii) For any fixed distinct keys $x_1, x_2,\dots, x_k \in D$, as $h$ is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), \dots, h(x_k)$ are independent random variables.
It is not obvious to me how one proves (i) from the above definition without explicitly assuming (ii) in the definition as well (and vice-versa). How is the definition sufficient for proving both (i) and (ii)?


texts: DFA to regular expression how to deal with 'sink state'

texts: Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink state and the edge from the sink to itself won't get any representation in the regular expression right? We can just remove those edges and stated at the beginning.. Am I right?


texts:
This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct.
Basically, I'm wondering if it is plausible for there to be a formal proof of P!=NP if ZF is consistent (obviously the converse is true). The idea is this: since proofs to sentences in ZF can be viewed as witnesses in an NP-language, if P!=NP then this means that for some fixed $k$ not all provable sentences $\phi$ of ZF have a proof of length $\leq {|\phi|}^k$. But if ZF is inconsistent, then every sentence of sufficient length has a relatively short proof derived from a fixed contradiction. So we get that P!=NP implies that ZF is consistent. So if we have a formal proof of P!=NP then this would imply through Godel's Second Incompleteness Theorem that ZF is inconsistent (and thus P=NP) as well. Is there a problem with this approach?


texts:
Here is Wikipedia's explanation of Horner's Method:

  Given the polynomial

  $$
p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,
$$

  where $a_0, \ldots, a_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x$, say $x_0$.

  To accomplish this, we define a new sequence of constants as follows:

  $$
\begin{align}
b_n & := a_n \\
b_{n-1} & := a_{n-1} + b_n x_0 \\
& {}\  \  \vdots \\
b_0 & := a_0 + b_1 x_0.
\end{align}
$$

  Then $b_0$ is the value of $p(x_0)$.

  To see why this works, note that the polynomial can be written in the form

  $$
p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)).
$$

  Thus, by iteratively substituting the b_i into the expression,

  $$
\begin{align}
p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\
& = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\
& {} \ \  \vdots \\
& = a_0 + x_0(b_1) \\
& = b_0.
\end{align}
$$

Question:

Is the point of this algorithm that we can now evaluate $p(x_0)$ without having to ever evaluate any of the values $x_0^2, \ldots, x_0^n$, and instead, we are able to just just iteratively compute $b_n$ through $b_0$, where by the time we eventually get to $b_0$ we are finally able to evaluate $p(x_0)$?

If this is the case, why is this useful? Why not just compute $p(x_0)$ the normal way?

EDIT: Is it true that using Horner's rule to compute a polynomial of degree $n$ takes running time from $\Theta(n^2)$ down to $\Theta(n)$?


texts: context sensitive language finite or infinite

texts:
let L be a CSL. (my understanding/ memory/ expectation is) the problem

  is L finite or infinite?

is undecidable.

where was this 1st proved/ published?
are there any cases in the literature of analyzing a CSL L in some "limited context" and determining whether it is finite or infinite? (also wondering about machine learning contexts.)

(brief background: the question can arise in analysis/ application of automated theorem proving. one might reduce a theorem "there exist an infinite x" to a CSL L which enumerates x and the question of whether L is finite or infinite.)


texts: Converting an NFA to regex using GNFA algorithm?

texts:
So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.

Given the following NFA:

Using the GNFA algorithm get the regular expression.

I understand that you would have the following for the first step(adding empty states):

The next step would be removing the state [q1] I would get:

Finally removing [q2] would get:

However the answers others have got is:
$(a \cup bb^*a)^*bb^*$
Which does not make sense as I got, $a^*b(b \cup aa^*b)^*$?
A GNFA(generalised nondeterministic finite automaton) is described as follows:

A GNFA is similar to an NFA but must obey certain rules:

It has only one accept state
The initial state has no transitions coming into it
The accept state has no transitions coming out from it
A transition can denote any regular expression, rather than just a
symbol from the alphabet Note that a symbol is a kind of regular
expression.

Furthermore, We may convert an NFA into a GNFA as follows:

Add a new start state with an ε-transition to the old start state
Add a new accept state with ε-transitions from the old accept states
If arrows have multiple labels, or if there are multiple arrows
between two states, replace them with the union (or) of those labels


texts: Difference between "functional programming languages" and "lambda calculus based languages"?

texts:
In "Can programming be liberated from the Von Neumann Style?", John Backus states:

  The main reason
  FP systems are considerably simpler than either conventional languages or lambda-calculus-based languages is
  that they use only the most elementary fixed naming
  system (naming a function in a definition) with a simple
  fixed rule of substituting a function for its name.

What surprises me about this statement is that I had the perception that functional programming languages are based on lambda-calculus. After reading the article, I still cannot understand this statement.


texts: $\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$

texts:
Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.

For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.


texts: How to construct object oriented programming in pseudo code?

texts:
I am studying a data structures course in which we have given many assignments on constructing data structures (like trees, arrays, and linked lists).

In class template, what kind of notation should I write for these operators (::,->) and the others operators which are used in C++? Can anyone elaborate more about writing pseudo-code for object oriented programs?


texts: Complexity of an optimisation problem in 3D

texts:
I have a collection $P \subseteq \mathbb{R}^3$ of $N$ particles and there is a function $f : P^2 \to \mathbb{R}$. I want to find which configuration of the system minimizes the value of $f$.

Can this problem (or similar ones) be reduced to TSP? Could you point me to literature on the topic?

In my application, $f$ is the atomic van der waals force, which for each pair of particles of atoms is attractive or repulsive depending on some predefined thresholds.

In addition, it would be great to have a list of concrete examples of problems that can be reduced to TSP.


texts:
I read the following in CRLS:

I don't understand the text in yellow. Why would radix sort not work so well if we sort by their most significant digit? What extra "piles of cards" is it referring to?

Perhaps I'm not able to follow the example with cards, and an example with actual numbers would be best.

In case it helps, sorting naively by MSD doe not seem to work, even if all values are d-digit numbers:

Input   (1)   (2)   (3)
        *      *      *
 321    132   321   321
 522    321   426   522
 132    426   522   132
 426    522   132   426

where (i) is the result of sorting the previous column by the ith-highest digit.


texts: Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent

texts:
I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution.

  Consider the following family of hash functions that map $w$-bit
  numbers to $l$-bit numbers (i.e. the range is $\{0,...,m-1\}$ where
   $m=2^l$):

  $\mathcal{H} = \{h_{A,b}|A\in \{0,1\}^{l\times w}, b \in
 \{0,1\}^{l\times 1}\}$, where $h_{A,b}(x) = Ax+b\mod 2$

  Show that $\mathcal{H}$ is $2$-wise independent but not $3$-wise
  independent ($\mathcal{H}$ is $k$-wise independent if for any $k$
  inputs $x_1,...,x_k$ and hash values $v_1,...,v_k$,
  $\Pr\limits_{h\in\mathcal{H}} \left( \bigwedge\limits_{1\le i\le k}
 h(x_i)=v_i \right)=m^{-k} $).

I'm first trying to show that $\mathcal{H}$ is $2$-wise independent. So consider any two inputs $x_1, x_2$ and hash values $v_1,v_2$. Then it's required that $\Pr \left( h(x_1)=v_1 \wedge h(x_2)=v_2 \right)=\frac{1}{m^2}$.

$$\Pr \left( h(x_1)=v_1 \wedge h(x_2)=v_2\right)$$

$$\Rightarrow \Pr\left( Ax_1+b = v_1 \mod 2\wedge Ax_2+b=v_2 \mod 2\right)$$

What about this equation shows that the probability is $\frac{1}{m^2}$? If we were trying to show $3$-wise independence, we would have:

$$\Pr\left( Ax_1+b = v_1 \mod 2 \wedge Ax_2+b=v_2 \mod 2 \wedge Ax_3+b=v_3 \mod 2\right)$$

Why is this not $\frac{1}{m^3}$?

I just don't know how to evaluate an expression like $\Pr\left( Ax_1+b = v_1 \mod 2 \wedge Ax_2+b=v_2 \mod 2 \wedge Ax_3+b=v_3 \mod 2\right)$. I've tried searching online for similar problems, but none seem to help with solving this one specifically.


texts: Finding constants C and k for big-O of fraction of polynomials

texts:
I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for  finding the constants $C$ and $k$ in the definition of big-O
$$
|f(x)| \leq C|g(x)|, x > k,
$$
when the function $f(x)$ is a fraction of polynomials.

I have tried to concoct my own method, but I am unsure of its correctness. I was inspired by the easy method of finding $C$ and $k$ for a polynomial where for example we can show that $x^3+2x+3$ is $O(x^3)$ by
$$
x^3+2x+3 \leq x^3+2x^3+3x^3 = 6x^3
$$
to find $C = 6$ and $k = 1$.

Now, for a fraction of polynomials I am unsure what to do with the denominator. My attempt at a general method is as follows. I would like to show that $\frac{x^4+x^2x1}{x^3+1}$ is $O(x)$. First I divide by the highest term in the denominator to get a $1$ in the denominator:
$$
\frac{(x^4+x^2+1)/x^3}{(x^3+1)/x^3} = \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}}
$$
Now I argue, somewhat analogously to the previous example, that the fractions in the numerator must be less than (when x > 0) x, and since a smaller denominator makes the expression smaller, setting all the terms in denominator except the $1$ to $0$, I obtain the inequality
$$
\frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} \leq \frac{x+x+x}{1+0} = 3x
$$
and I find $C = 3$ and $k = 1$.

Now my question is, does this homebrewed method actually work or is it complete nonsense? And if it is nonsense, does anybody know of another general method for finding $C$ and $k$ in instances like this?

Note that I need to find the constants $C$ and $k$, not just show that a given function is big-O of some other function, and the students have had no course in calculus, so I can use no concepts from there, such as limits.


texts: Floating Point Systems - Rounding Error in Taylor series

texts:
I have a question about  rounding error. I have created a function to approximate exp(x) by summing the terms of its taylor series until the sum stops changing. (That is, 1 + x + x^2/2! ...).

This function works well for seemingly any positive value of x that i have tried, but when i try for instance -30, it does not give me anything even close to what exp(-30) gives me.

I am aware of how to solve this problem, but I'm more curious as to why this happens. Does it have something to do with the alternating + and - signs when summing the series? Thank you.


texts: Making an array increasing by modifying elements

texts:
I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, needed to make the array strictly increasing. That is, we want to find an increasing integer array $b_1,\ldots,b_n$ while minimizing $|a_1 - b_1| + \cdots + |a_n - b_n|$.

By considering the array $a'_i = a_i - i$ instead, we can replace the condition of strictly increasing but the condition of nondecreasing.

The solution that I thought of was naive (I am a beginner in competitive coding), so I read the editorial. I understood the dynamic programming solution but then I found a blog post that describes an $O(n\log n)$ solution to the problem.

I tried hard to understand the details, but there are two things I don't understand: why they consider slope, and why they have a recurrence relation at the very beginning.

After looking at the implementation, basically what they did I think was just to consider the largest element found so far in the sequence, and keep it as the key point. Any other element that is less than that number is changed to that number, rather than considering decreasing the larger number, because this reduces the chances of further modification in the array. Is there something I am missing which was the point of whole mathematical slope analysis? I would appreciate if anybody could shed some light in simple manner as to what the blog tries to say or explain the why this approach is correct in simple manner.

Here is the implementation in pseudocode, where the goal is to make the array nondecreasing rather than strictly increasing, and we are only interested in computing the cost (rather than actually modifying the array):

Initialize cost to zero.
Initialize a priority queue $Q$ with $a_1$.
For $i = 2,3,\ldots,n$:

Add $a_i$ to $Q$.
If $\max(Q) > a_i$:

Add $\max(Q) - a_i$ to the cost.
Remove $\max(Q)$ from $Q$.
Insert $a_i$ to $Q$.

Return the cost.

The priority queue supports the following operations in $O(\log n)$:

Compute the maximal element.
Remove the maximal element.
Add an arbitrary element.


texts: Is it possible to define a DFA for the language of words having exactly one double letter?

texts:
Consider the language $\{ w \in \Sigma^*~|~ w~\text{contains exactly one double letter}~\}$. For example,
$baaba$ has exactly one double letter, but $baaaba$ has two double letters.

Suggested answer for the case where $\Sigma = \{a,b\}$ (even if it's an RE not a DFA): $(\epsilon \cup b)(ab)^*aa(ba)^*(\epsilon \cup b) \cup (\epsilon \cup a)(ba)^*bb(ab)^*(\epsilon \cup a)$.


texts: Regular set of the "does not contain" kind

texts:
Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses
$L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$?
Well, the part that states that w must end with 00 is easy and I (think I) managed to find the regular set for it. But I can't modify it so that w won't contain 11.
I didn't find many articles about this subject on the internet, and the ones I did didn't help me much in this "does not contain" kind of problem. So it'd help a lot if you guys could mention some articles on regular sets to me.


texts:
If $e = \{u, v\}$ is a cut edge with $\deg(u)$ and $\deg(v)$ both at least 2, then $u$ and $v$ are cut vertices.

I want to prove or disprove this statement, but don't know how to proceed. I do know what goes wrong when one of the degrees is smaller than 2.


texts:
I'm trying to prove a problem that a friend sent me, he is saying that my solution is not good and I wanted to ask if he is correct and im wrong , and if so why?
here is the questions:

$L=\{<M>| \text{ M accept all languages with no more then 1 palindrome}\}$

prove that L is not decidable by showing that :
$H_{TM} \leq_T L$

(Definition of $H_{TM}$)

$H_{TM}=${$((<M,w>)|$$M$ stops on $w$}

here is my solution:

define $M_P$ machine that runs $M$, on $w$ ,if $M$ stops ,$M_P$ will accept if it get an input=131 otherwise loop (accept only one palindrome).

this is my function:

$$
f(<M,w>) = \begin{cases} \Sigma^* & \text{ } if <M> Bad_.Encoding \\M_P & \text{if }<M,w> \in H_{TM}.\end{cases}
$$

my idea is the next:
if   we have bad encoding , we put $\Sigma^*$ which has more then 1 palindrome, else , we run $H_{TM}$ with $<M,w>$ , if we accept we put our $M_P$ which will accept for our L.

thank you!


texts:
struggling with this question from an exam:

input:

  DAG G=(V,E). each edge  $e_i$ has weight $w_i\in \text{{0,1,2,3}} $

  Two vertices : s,t

  Number: k

output:

  A path from s to t with total cost k (if exists)


texts: Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

texts:
Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise}
\end{cases}$$

where $\varphi(N)$ is Euler's totient function.

Can I somehow express $\varphi(N)$ as $N/b$, so I can apply the Master Theorem and resolve this recurrence?

You may assume $\varphi(N) = (p-1)(q-1)$, if it's easier that way.  You may also assume, if it helps, that $p$, $q$ are safe primes, that is, $p = 2p' + 1$ and $q = 2q' + 1$.  (Assume anything that makes the problem easier.  For instance, you can replace the function $\lg^3(\varphi(N))$ with any other that makes the problem easier, but do so only as a last resort.)


texts: What is an example of a weakly universal hash function that is not pairwise independent?

texts:
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :

$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.

A family of hash functions $H_s$ is said to be strongly universal if for all $x \ne y$ and $k, \ell \in [m]$:

$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

What is a concrete example of a hash function family which is weakly universal but not strongly universal?


texts: In some literature, as well as in Wikipedia, the middle term parameter m of Mersenne twister is called "number of parallel sequences". Why? What is meant here by "parallel sequences"?


texts: Big O analysis for problem where number of items searched is unknown

texts:
Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in the array. With this algorithm, chances are, you will not search the entire array because you will either find the square root or you will find that the square root is not in the array.

As such, you are searching only a fraction of the array, which lets say has M elements. Does this mean that the big O is still O(M), even though you are not searching all of the elements?


texts:
Edit: can someone provide clear answer with all details
Given:
$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$
I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)$
Using a set of complicated equations I found and proved that $a=9/10$ is the correct answer (for sure)
But how I can prove that using recursion tree?
Here I did all of the calculations:


texts: Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?

texts:
There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-order.

What do those terms mean? How do I properly categorize an algorithm as pre-order, in-order, or post-order?


texts:
I am trying to work out the recurrence relation for Ternary Search. This is what I came up with:

C(n) = C(n/3) + 2

However, I talked to my professor and he said it's not correct. He says that we need to take all of their cases into account. This part confuses me a little bit, can you please clear it for me?

Thank you.


texts: Does a path exist going through each color only once?

texts:
I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once.

I think this problem can be formulated using network flow. Somehow a penalty can be placed on nodes of the same color that makes the flow 0 or infinity if a node is repeated.

Thanks!


texts: Greedy Algorithm to return multiple optimal solutions

texts:
How would one go about enumerating all the optimal answers for interval scheduling?

Not sure what to begin with, my guess is to use the other approaches i.e. earliest start time, shortest interval and fewest conflict in conjunction with the optimal implementation which is to use the earliest finish time approach.


texts:
I've been thinking about embedded languages (domain-specific or otherwise), and in particular the approach where we define a datatype to represent terms of the embedded language, e.g. (in Haskell):

data Expr = Numeral Int
          | Apply Expr Expr
          | Lambda String Expr
          | Var String
          | ...

We then provide a library of functions which allow us to write programs, like plus 10 5, but when "run" they don't actually produce the 'answer' (15), they instead produce a representation of that program in the embedded language, like Apply (Apply (Var "plus") (Numeral 10)) (Numeral 5).

My question is: can we implement a general-purpose, high-level programming language, like Haskell, such that the "compiler" is actually a set of library functions, "compiling" is just interpreting our program, and the resulting value is machine code (or Javascript, or whatever our compilation target is).

Another way to think about this: in Lisp-like languages, we can create new language constructs using macros, which get "expanded" into other macro calls and eventually down to "special forms" implemented with an interpreter/compiler. From this perspective, my question would be: is it possible to make a Lisp where the only special forms are (representations of) machine code, and the whole "user-facing" language (function definition, calling, branching, etc.) is just a set of macros? In such a system, macro-expanding a program would result in a compiled binary. I'm willing to ignore the "dynamic"/reflection/etc. features found in "real" Lisps.

Another way to think about this: assembly languages get macro-expanded into machine code; are there any any assemblers which do/could provide "high-level" features, like higher-order functions, pattern-matching, garbage collection or linear types, etc.?

Is there some insurmountable difficulty with this (e.g. linking?)? Is it something that's been done? Things which seem related, but slightly different:

Forth seems to 'bootstrap' itself in a similar way when executed, but doesn't (in my limited experience) seem to "compile down" to a 'self-contained binary'; rather, it either runs "dynamically" (i.e. the code we write gets executed 'as is'), or it gets compiled into a form with an embedded interpreter.
The IO approach of Haskell, Idris, etc. is similar, in that Haskell can be seen as a macro language for constructing "IO programs", but it's not quite the same: our Haskell code isn't "fully expanded" by the compiler: we can write pure functions which only get executed at runtime, and even when things do get inlined/fused/etc. it's because of 'compiler magic' rather than the language's semantics.
The Nix language is purely functional and turing complete, and its programs evaluate to give "derivations", containing an environment and build script for some 'package'. Derivations can, optionally, be sent to the nix-build tool for execution. Could we make a similar language which evaluates to give a "machine code" (or "unlinked assembly") value, which we can subsequently pass to an assembler/linker/etc.?

In such a system, our program would be instructions for the "compiler" (the interpreter we run to get the resulting binary), hence we could implement things like instrumentation, optimisation, cross-compiling, etc. as library functions, rather than having to update some separate, monolithic program like GHC.


texts: Undecidable problem intersection of two DCFL languages is DCFL?

texts: We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an intersection of the languages of A and B. This problem is known to be undecidable. But I can't find a proof for it.


texts: Algorithm for optimal spacing in intervals

texts: Is there an algorithm to optimally space points within multiple intervals? Optimal in this case means maximizing the smallest distance between any two points so that each pair of points has at least distance X. For example, in the intervals (1,3) and (5,7) you can space out three points with a distance of at least 2 (at 1,5, and 7). But you can't space out three points with a distance of at least 3. Is there an easy way to do this with a program?


texts:
A bin is called full if it contains at least $k$ balls. Our goal is to make as many bins as possible full.

In the simplest scenario, we are given $n$ balls and may arrange them arbitrarily. In that case, obviously the best we can do is pick $\lfloor n/k \rfloor$ bins arbitrarily and put $k$ balls in each one of them.

I am interested in the following scenario: we are given $n$ pairs of balls. We have to put the two balls of each pair in two different bins. Then, an adversary comes and removes one ball from each pair. What can we do to have the maximum possible number of full bins after the removal?

A simple strategy is: pick $\lfloor n/(2k-1) \rfloor$ pairs of bins. Fill each bin-pair with $2k-1$ ball-pairs (each bin contains $2k-1$ balls, one ball from each pair). Then, regardless of what our adversary removes, we have in each bin-pair at least one full bin.

Do we have a strategy that achieves a larger number of full bins (more than $\lfloor n/(2k-1) \rfloor$)?


texts: If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?

texts:
I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear congruential generator, which is an algorithm that based on some fixed constants and this seed through some mathematical computations gives the final pseudorandom output.

But what are the disadvantages of using this time directly as a pseudorandom number?


texts: On $NP=\Sigma_2^P$ from non-deterministic time?

texts:
We know $NP=\bigcup_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma_2^P=NP^{NP}$.

Does $\Sigma_2^P\subseteq\bigcup_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-deterministic $O((n^k)^c)$ time which is  non-deterministic $O(poly(n))$ time)?
Is there a reason we cannot conclude $NP=\Sigma_2^P$ from this?

From this $NP=PH$ should hold.


texts: How to partition the rows of a matrix in such a way that every column satisfies a given condition?

texts:
The input is: Given a matrix $\mathbf{A}=\left[a_{ij}\right]$ of nonnegative integers for all $i\in\{1,\ldots, m\}$ and $j\in\{1,\ldots, n\}$ (where $n<m$). Nonnegative integers $V_j$ for all $j\in\{1,\ldots,n\}$.

The question is: Find $n$ disjoint sets $S_j$ of $\{1,\ldots,m\}$ such that
$$\bigcup\limits_{j=1}^{n} S_j=\{1,\ldots,m\},$$
$$\quad\quad\quad\;\,\sum_{i\in S_j}a_{ij}\geqslant V_j, \forall\,j\in\{1,\ldots,n\}.$$

So for example, given the matrix

$$
\begin{pmatrix}
7 & 4 & 3\\
3 & 2 & 7\\
2& 3 & 4\\
1 & 1& 5\\
6 & 10 & 8
\end{pmatrix},
$$
where $n=3$, $m=5$ and $V_1=12$, $V_2=10$ and $V_3=5$.

Then, a solution is $S_1=\{1,2,3\}$, $S_2=\{5\}$ and $S_3=\{4\}$.

I think the difficulty of solving this problem comes from the fact that we would like to partition the rows of a given matrix in such a way that every column satisfies a given condition.

Even though the problem seems related to the exact cover problem, I cannot find a good way to solve it.

Can you suggest a method/algorithm that finds solutions to such problem? If it is a known problem, do you know any reference?


texts: Describe in English the pattern in the following regular expressions

texts:
Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible

#1 (x (yyy + x)*)*
#2 (c (cc)*d(dd)*)*

for number 1 I got all words in which when y is in the word it can only appear in blocks that are divisible by 3(0,3,6,9, etc.)

the second question I can not see any type of pattern.

I would like to know if the first one is correct, and if what pattern is on the second one?

Thanks


texts: Trying to understand Kempe's algorithm for Graph Coloring

texts:
I am trying to understand Kempe's algorithm to $k$-color a planar graph. This is what I understand till now:
Trying to 6-color a planer graph ($k=6$)

Find a vertex of degree <= 5 ($k-1$)
Remove this vertex
Color the rest of the graph using a recursive call
Put the vertex back, since its degree was at most 5 ($k-1$), we still have at least 1 color left to color this vertex

I understand this procedure but I was curious about the first step: finding a vertex of degree at most $k-1$. What would happen if there is no such vertex in the graph? For example, all vertices have a degree $> k$. In that case will the algorithm fail?


texts: shortest paths algorithm - why backtrack from the end node instead of starting from the starting node?

texts: I was watching a dynamic programming video by Erik Demaine . He says here https://youtu.be/OQ5jsbhAv_M?t=2133 , finding the shortest paths from S to V for all V, by guessing the node after the starting node is not the right approach, and instead should guess the node before the last node. I didn't understand his explanation. Can someone explain better why find the path backwards? It seems to me that you should get the same answer either way and both approaches are equally good.


texts: Most probable value of randomized procedure output

texts:
Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \{0, 1, \ldots, m - 1\}$ with a flat probability distribution. I have the following procedure:

W := an array of length m full of 0s
for i in 0, 1, ..., n - 1; do
    (x, y) := (rand(), rand())
    W[y] := max(W[x], W[y]) + 1
x := 0
for i in 0, 1, ..., m - 1; do
    if W[i] > x; do
         x := W[i]
return x

My question is: what is the most-probable value of $x$? I'm not even sure where to begin with the analysis here, due to the probabilities involved.


texts: Incentive for block creation in a private blockchain

texts:
Bitcoin miners are incentivized to produce valid blocks via a trasactional reward. But let's say I wanted to implement blockchain as part of my private data system. Who would my miner's be? I think could just have one automated miner (on a dedicated machine) with the proof-of-work difficulty being set to something very easy. But then I'm wondering, what's the point? Is there anything to gain by using a blockchain like this?

In other words, can someone please give an example---no matter how crude---of how someone could use a private blockchain to log transactions, or whether such a thing has any practical benefit to the users?


texts: Is the union of two non-regular context-free languages always non-regular?

texts:
I had this question in my HW:

  Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular.

My intuition is that it is wrong. I thought about the following two languages:

$L_1 = \{a^ib^jc^k : 0 \leq i \leq j \leq k\}$ and
$L_2 = \{a^ib^jc^k : j<i \lor j>k\}$.

The union of these two languages is $a^*b^*c^*$ which is regular, but I didn't succeed to prove that $L_2$ is not a CFL (tried with the pumping lemma and stuck in the case that $vxy$ contains two types of letters).

Am I right with my intuition? if do so, how can I prove that $L_2$ isn't a CFL, or which other two languages disprove this claim?


texts: compute a gradient with "minimal" colorstops from a ordered set of RGB colors

texts:
I got a array of colors that are closely related = most of the time there is no sharp transition between color[n] and color[n+1].

Exemple of such an array of colors
[0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1.0,.8,.6,.4,0.2,0]

You'll notice that there are 3 "special" values. The colors
slowly increase from value 0 to 1 (in 10 steps) then
decrease more rapidly from 1 to 0 (in 5 steps).

So our array could also be described this way :

an array of 16 colors where
Color[0]  whose value is  0 evolves linearly until
color[10] whose value is  1 evolves linearly to
color[15] whose value is  0

I don't really care about the length of my initial array. It will be  stretched (interpolated) so instead of using indexes it makes more sense to use percentage values
index 0  /15 = 0%
index 10 /15 = 66%
index 15 /15 = 100%

so the initial array could be rewritten like this
[{0, 0%}, {1, 66%}, {0, 100%} ]

This last notation is close to what is called a gradient in svg or css. The special color are named "colorstops" and gradients are written this way
linear-gradient(black 0%, white 66%, black 100%);

One could notice that some gradients are equivalent

linear-gradient(black 0%, white 100%) =
linear-gradient(black 0%, grey 50%, white 100%) =
linear-gradient(black 0%, lightgrey 25%, grey 50%, darkgrey 75%,  white 100%)

like

interpolation[0, 1] =
interpolation[0, .5, 1] =
interpolation[0, .25, .5, .75, 1]

So my challenge is to go from
[0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1,.8,.6,.4,.2,0]
to
linear-gradient(black 0%, white 66%, black 100%)
and not the naive
linear-gradient(
 black    0%,
 grey++++ 6%,
 grey+++  13%,
 grey++   20%,
 grey+    26%,
 grey     33%,
 grey-    40%,
 grey--   46%,
 grey---  53%,
 grey---- 60%,
 white    66%,
 grey---  83%,
 grey-    80%,
 grey+    86%,
 grey+++  92%,
 black   100%)

The expected size of color array is no more that 2000 RGB colors and the goal for color-stops is no more that 10 and ideally 2.

EDIT
 in fact what i want to do is compute the blue lines like on the following graph


texts: Bounds on tape alphabet size of a Turing Machine encoding

texts:
What is the max possible ratio between the tape alphabet size and the total encoding size in an asymptotic sense? Say if I take some TM and add more and more symbols to its tape alphabet, will the encoding size grow linearly? or might it grow exponentially? Or being more specific:

Let $L \subseteq \{ \langle M \rangle : M$ is a TM$\}$, and let $D$ a TM deciding L with worst case time complexity of $\Theta(f(n,k))$, where $k= |\Gamma|$ and $\Gamma$ is the tape alphabet of the input TM.

Does this imply D runs in $\Theta(f(n,n))$ where $n$ is the input size? (i.e, $n=|\langle M \rangle|$)


texts: Constructing a tree from disjoint graphs

texts:
I will preface my question with the definition of a simple tree that applies to my question:

  A simple tree is an undirected and connected graph with no cycles.

I am having difficulty coming up with a compelling argument that a tree of the above definition can be constructed by taking a set of disjoint valid graphs and adding a vertex between each of them. The practice problem states:

  Prove that some graph $G$ is a tree if and only if it can be constructed from a set $X_1, X_2, \dots, X_i$ of disjoint valid graphs by adding a new node adjacent to one node from each of $X_1,\dots, X_i$. A single node is a valid graph.

I'm confused whether this question is asking me to prove that two graphs, or trees ("valid"), can be made into one tree by adding a node and adding edges from one preexisting node from each of the trees. If that is how the question should be interpreted, then is it enough to prove that the new tree (or "graph," I guess) has no cycles, and is connected?

I'm new to graph theory and I'm wondering if you can help me understand it.


texts: How to define the natural numbers as a W-type?

texts:
I'm having trouble understanding the rules for W-types in type theory as defined here: https://ncatlab.org/nlab/show/W-type#wtypes_in_type_theory

Can someone give an example of how these rules could be used to define a simple W-type such as the natural numbers? What would $A$ and $B$ be in the formation rule for instance?


texts: Find the Maximum rows having all ones in the binary if you are allowed to toggle columns in the matrix for exactly k number of times

texts:
A binary matrix of nxm is given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s.

for eg, n=3, m=3,

        1 0 0

        1 0 1

        1 0 0

if k=2, then we will toggle column 2 and 3 once and we will get rows 1 and 3 with 1 1 1 and 1 1 1 i.e. all 1’s so answer is 2 as there are 2 rows with all 1’s.

if k=3, then we will toggle column 2 thrice and we will get row 2 with 1 1 1 i.e. all 1’s so answer is 1 as there is 1 row with all 1’s.


texts: Is the calculation of infinite sums solvable by a computer?

texts: The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this problem been solved using a computer? Or, has it been proved to be undecidable? Or is it open?


texts: How do set partitions get mapped by restricted growth functions

texts:
I am reading Skiena but do not have a formal background in Computer Science. On page 457 he discusses generating set partitions via restricted growth functions. Here's specifically what he says:

    Set partitions can be generated using techniques akin to integer partitions. Each set partition is encoded as a restricted growth function a1,...,an where a1 = 0 and ai <= 1 + max(a1, ..., ai). Each distinct digit identifies a subset, or block, of the partition, while the growth condition ensures that the blocks are sorted into canonical order based on the smallest element in each block. For example, the restricted growth function 0, 1, 1, 2, 0, 3, 1 defines the set partition {{1, 5}, {2, 3, 7}, {4}, {6}}.

Can someone walk me through how this mapping works? It seems to me that a2 should be less than 1 + max(0, a2). But how does that determine a2? How do I get from 0, 1, 1, 2, 0, 3, 1 to that set of partitions? I don't see it at all and would appreciate any explanation or hints.


texts: Linear order minimizing weighted distance from special element

texts:
Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)$, where the weights $w_i$ are given, and the distance is computed as the number of beads between the two corresponding beads.

The minimum cost for every position of $b_0$ can be calculated in linear total time (plus $n \log n$ pre-processing time to sort the weights), by noting that the optimal solution is to pair up the beads on either side by increasing weight, with a residual 'tail' on the longer side, and working out how the cost changes as you shift $b_0$ along.

What if some of $b_1,\dots,b_n$ are fixed in given positions?

Obviously quadratic time is possible by solving each sub-problem independently, but is there an incremental algorithm akin to the case without any fixed beads?


texts: Complexity of membership testing for finite-regular languages

texts:
A language $L \subseteq \Sigma^*$ is finite-regular if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Given a finite-regular language $A_L$, am I guaranteed that there exists a polynomial-time algorithm $A_L$ that recognizes $L$?  In other words, I want an algorithm such that on input $x$ it returns true or false according to whether $x \in L$ or not, and the running time is polynomial in the length of $x$.  Is this guaranteed?

Note that the number of states of the complete DFA accepting such $L$ may be $O(|\Sigma|^n)$ so any trivial algorithm actually constructing the full DFA would not be polynomial time. However the number of accepting final states is $O(1)$, which leads me to believe there is some shortcut available here.

Thanks to Yuval Filmus for formalizing this language class, and explaining its closure properties.


texts: Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models M of a logic formula f and summing their weights w(M) is #P. What happens if the weight is a function of the model and the task of computing the weight w(M) given M is in itself #P? Whats the complexity of the total problem?


texts: Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

texts:
I am interesting in the asymptotic rate of growth of the following recursion:

$$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$
with base case $T(1) = 1$.

I'm having trouble of solving this recurrence problem, it seems much more tricky than I initially thought, and I'm totally stuck after doing some unrolling. What is a good way to approach this question?


texts: "Reshaping" vs Polymorphism In Data Wrangling

texts:
A lot of the work in data science -- machine learning in particular --involves "reshaping" arrays, tables, and other data structures.  These data transformations are not really lossy transformations (except for subsets/selective views), but rather simply getting existing data into a different form acceptable to existing algorithms.
This seems to be a big step backward in computer science, away from data abstraction.  In particular, it seems polymorphism has somehow been forgotten in all the work geared toward morphing the data into the proper form.
Am I missing something about this problem that renders it particularly immune to the application of mature technologies to hide data representation from the abstract functions?


texts:
I'm currently trying to evaluate a CTL* expression and am not sure how to stepwisely evaluate the queries.
For example I have EFG p. This means something like 'there is a path where eventually there exists a state s where from there on, globally p holds true'.

Globally means that for all successors of a state on all paths starting at this state a certain property holds true.

Applied to the example above, this would mean when evaluating EFGp on a model with init-state s0, that there exists a path from s0 to a state s' where from there on all succeeding paths have the property p.
But wouldn't this imply that this is equivalent to EFAG p?

Is it in general possible to evaluate such queries stepwise (operator by operator) or do I have to consider all operators at once?

best regards


texts: What kind of small Turing machines evade current attempts to prove their halting?

texts:
On the german Wikipedia, I read that:

Der Bulgare Georgi Georgiev veröffentlichte 2003 eine Untersuchung, in
der er fleißige Biber daraufhin analysierte, ob sie anhalten würden
oder nicht.[2] Für {\displaystyle n=5}n = 5 entzogen sich lediglich
knapp über 40 fleißige Biber einem gesicherten Ergebnis, da sie
aufgrund besonderer Verhaltensweisen nicht mit den von Georgiev
angewandten Methoden abschließend zu analysieren waren.

The same sentence doesn't appear in english, as far as I saw. The summary is that in 2003 BB(5) was almost determined, but there were still about 40 Turing machines (out of around 60 trillion) that evaded the proof regarding whether they halt.
Is this still the case or was the number at least reduced? What made those machines so difficult to analyze?