texts: Rechecking contiguous characters (as in run length encoding)

texts:
So I have a fun little problem. It will take a minute to explain, but the situation is conceptually very simple. Suppose you have a string of characters, which is interpreted as groups of one or more contiguous characters. This is for run length encoding or something. For example:

  zz22344a is two z's, two 2's, one 3, two 4's, and one a.

Once you've parsed the original string, you retain only the characters and sizes in an array.

struct Run { char whatChar; int length; }

Run* runArrayVar;

void parseIntoArray(char* sourceChars);   // creates runArrayVar

I won't put the implementation of parseIntoArray() here because it's trivial to do with a loop, but I'll assume that arrays are null-terminated, although in the problem they don't have to be. Here is the problem part. I want to implement a function like this:

void alterArray(char* newSourceChars, int changedOffset,
                int changedLength, int changedCharsAdded);

This responds to a change in the source text. Included is the new text, the beginning and length of the altered area, and for reference, how many extra characters were added. For example, take the original zz22344a. If the substring 223 was pasted over with 23_44, then the new string would be zz23_4444a and the new array would be two z's, one 2, one 3, one _, four 4's, and one a.

I could get the new runArrayVar naively by just calling parseIntoArray, but I want to be less naive: I want to step through and only change the parts of runArrayVar that need to be changed. Finding the first changed element is pretty easy; skip through until you find one that overlaps changedOffset (you need to test one extra char after the element). After that it gets dicey and I can't figure it out. Take the above example:

zz needs to be re-checked because the character right after it might have been changed to a z. It wasn't, so it remains zz. Now we're at offset 2.

22 is rechecked, and it turned into 2. So OK. Now we're at offset 3.

3 is rechecked, and it's the same. So we're at offset 4.

44 is rechecked, and apparently turned into an underscore. So we're at offset 5.

At this point we're still looking at characters that have changed, and we're at 4444. According to the previous logic, a turned into 4444. OK. Now we're past the characters that have changed, and our array still has an element with one a left over. I can keep parsing and terminate the array when I hit the end of the string, but suppose that a was actually a million as in a row. The algorithm should be able to reason that it doesn't have to do any more work and terminate. If you look at the example, there is nothing you could have changed that particular section into that would influence the a.

This is difficult. I've tried it a lot of different ways and I can't figure out exactly when the algorithm needs to terminate. Please let me know if you have any ideas!


texts: minimum number of nodes that traverse all the graph

texts:
In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover problem nor dominating-set problem since we don't need to select node 3. We say that, if we select node 0, we can go to node 1 from there and if we select node 2, we can go to node 3 and then node 4 from there.

Also, the number of nodes can be up to 10^5 and the algorithm's runtime must be 1 second or less. Any suggestion would be useful.


texts: Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

texts:
I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary tree whose levels are all full except for the last one in which all the nodes are as far left as possible.

I thought of proving it using induction but I'm not really sure how to do so. Any ideas?

UPDATE

Well I made somewhat of a progress but I also got a somewhat different result, here's what I did:

Let $T$ be an almost complete tree of height $h$ meaning that in the level of height $h$ there should be at least 1 node. Considering the fact that every height has double the number of nodes of the previous level we can derive that $T$ has the least possible number of nodes in the case that at $h$-level there is only one node. (1)

In that case the number of leaf nodes is

$l=2^{h-1}-1+1 \Rightarrow l=2^{h-1}$ and the number of total nodes is

$n=2^{h-1}-1+1$

$\Rightarrow l=2^{h-1}=\frac{2(2^{h-1}+1)}{2}=\frac{n+1}{2}$

$\xrightarrow{(1)(2)} l \geq\frac{n+1}{2}$

Now, I'm getting a bit closer but not really there yet. First problem is that I got $l \geq \frac{n+1}{2}$ and not $l \geq \frac{n}{2}$ which from what I understand stands only in the specific case that $h=1$. Second problem is that this doesn't seem like a formal proof... Any tips/suggestions?


texts:
I'm in an OS class now. I've been wrestling this problem for a while and can't convince myself of a solution. My professor is very busy and hasn't made time to help. Also, this question is from an example exam, not something I would be graded on.
In this question, we're given a virtual address to translate: 0xFEC. We're also told to use segmentation in accordance with the table and a 14-bit address. Looking at our address in binary, we have 0000 1111 1110 1100. We'll disregard the two most significant bits, as instructed giving 00 1111 1110 1100.
Taking the two leading bits as our segment tells us to use the base for the Code section, which is given to be 12. Then, we go to decimal and add.
dec(00 1111 1110 1100) + dec(12K) = ...
7018 + 12,288 = 19306
The thing that tells me this is incorrect, is that the number 7018 which is approximately 7K is much greater than 3.6K (the given size of the code section). :/
I'm really lost here, and I haven't found any examples of people moving addresses with segmentation or with decimal end numbers.
I think I'm wrong when interpreting the addition, but I'm not sure how.


texts: What does it mean to be Turing reducible?

texts:
I'm confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not.

$A \leq B $ Means that A is Turing reducible to B. This means that given an oracle for Machine B, A can be solved.

I'm confused in the case of SUPERHALT which decides whether a Turing machine with access to the HALT oracle halts or not. I feel like SUPERHALT is reducible to HALT because I can just put any Turing machine into a HALT oracle and then put that result into another HALT oracle.

So in summary I believe:

Given a Turing machine M and input x $\epsilon \{1,0\}^*$ and oracle $HALT$, $$SUPERHALT(M(x)) <_T HALT(M(x))$$ because $$SUPERHALT(M(x)) = HALT(HALT(<M(x)>)$$
Which is wrong, but I just want to know what I'm misunderstanding.


texts: Encoding two 6-bit positive integers compactly

texts: Is it possible to encode two 6-bit wide positive integers a and b guaranteed to be in [0, 63] in a way that a and b are recoverable -- in fewer than 12 bits? We could obviously concatenate the binary representations (a << 6 | b). The scheme would have to allow any two arbitrary values within the given range. Can we do better than 12 bits?


texts: What is the difference between "information model" and "conceptual model"?

texts:
I am trying to figure out the difference between information and conceptual models. For me, both terms seem to mean be the same, but I cannot find a reference where this is established. They are never used together; maybe because they are from different domains?

My question is: What is the difference between information model and conceptual model?

Definitions

Conceptual model:

  A domain consists of objects, relationships, and concepts we commit
  ourselves to a specific way of viewing domains. [...] In the field of
  information systems, this commitment to viewing domains in a
  particular way is called the conceptual model. [Antoni Olivé. 2007.
  Conceptual Modeling of Information Systems. Springer-Verlag, Berlin,
  Heidelberg.]

Information model:

  An information model is a representation of concepts, relationships,
  constraints, rules, and operations to specify data semantics for a
  chosen domain of discourse. The advantage of using an information
  model is that it can provide shareable, stable, and organized
  structure of information requirements for the domain context. [Y. Tina
  Lee, Charles R. McLean and Yan Luo, Information Modeling and Model
  Implementation. In: Proceedings of the International Simulation
  Conference, Italy, 2006]


texts:
Thanks to anon for contributing this wording:

Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is $|\pi(i)-\pi(j)|$. I want an algorithm which takes as input a (possibly only-partially-filled in) $n\times n$ array $D$, and outputs a permutation $\pi$ that maximizes the number of entries common to both $D$ and $A(\pi)$.

Wording I can follow:

I'm looking for an algorythm that yields a permutation $P$ of the given set $L$.

Where $P$ minimally violates a given set of constraints $C$.

Where constraints $C$ each specify an absolute offsets for the indexes of a pair of elements of $L$.

For example:

Where:

$L = \{w, x, y, z\}\\C = \{\{w, x, 2\}, \{y, w, 1\}, \{y, z, 2\}\}$

Then a valid answer would be $P = \{w, y, x, z\}$

Because, as described in $C$:

$w$ and $x$ are now $2$ "index positions" apart.

$y$ and $w$ are neigbours at $1$ apart.

$y$ and $z$ also being $2$ apart.

The data for $C$ may contain contradictions, therefore the result may be an estimate.

Q: What is a good way to solve this?

I wondered about an approach where $L$ values are placed randomly along a 1D line. $C$ describing the end connections and rest length of connecting springs. Simulated until at rest. Could this produce a reasonably accurate result?

What other aproaches are recommended for finding $P$ from $L$ and $C$?


texts: Time complexity of subset sum problem with reals instead?

texts: It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete still or harder (NP-hard)?


texts: Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

texts:
Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Consider the LP:

  $\max \lambda$

  s.t: $p_i + \lambda \le p_j + c_{i,j}$ where $(i,j)\in \mathcal A$.

I've shown:

The LP is feasible.
If $(\lambda,p)$ is a feasible solution then the directed cycle mean
cost of every directed cycle is at least $\lambda$.
The LP has an optimal solution (doesn't contain a line and $\lambda$
can't be greater than the maximum cost).

Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.

I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?


texts:
prove or disprove

$$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$

I have no idea about where to begin.

what are the theories which should be used here?


texts: Design a DFA which accepts words with sorted letters

texts:
I have just started learning Theory of Computation and have come across a question which I am not able to solve.

The question is as follows:

Design a DFA that reads a word (character strings) and decides whether the letters
of the word are in sorted order.
For example: 'adept' and 'chilly' have their words in sorted order but 'baby' doesn't.

How should I design a DFA for this language?

What I have tried:

I think there must be two states.

1) While the DFA is scanning the word, the state (q1) will transit to itself
if it reads a letter greater than or equal to previous letter read.

That is if the current_letter_read >= previous_letter_read then
q1 transits to itself. Otherwise, there is no action.

2) If '\0' is encountered, then the DFA transits to the final accepting state.

But in DFA is it possible to do so? How should I draw a DFA for this?
I got stuck at this point. Am I missing some basic concept that I should know?


texts: Fundamental representation of data relationships?

texts:
This is an offshoot of this question Which is more fundamental: key-value or subject-predicate-object?

Is there any fundamental, hypothetical or practical, representation of data relationships?

Both Key-Value and Subject-Predicate-Object describe pretty well relationships between data in any format. And any relationship can be reduced to be represented by either of them. Is there any theory behind this?


texts: which neural network is good for predecting the value of strings

texts:
I have a dataset that contains some strings. A numeric value is assigned to each string.
I want to develop a machine learning (deep learning) model to get a string and predict its value.
What neural network do you suggest for this model? Should I use RNN (LSTM)?


texts: Why would you introduce the goto statement into a modern language?

texts:
I just found out something really quite extraordinary.  While looking through Stackoverflow, I came across a question about removing goto from a php function.  PHP doesn't have goto I thought and looked it up on php.net.

It turns out I was sort of right.  PHP introducted goto in version 5.3 which was release in 2009.  PHP didn't start out with gotoit actually introduced it into the language in 2009!

Why on earth with all the horror stories we have from 40 years of bad programs written with goto in other languages would php actually decide to introduce it?

The php.net website even has this XKCD image suggesting no programmer should ever use goto.

Question:

What possible reason from a technical point of view could there be for introducing a the goto feature, which I nievely thought had been vanquished from modern computer programming languages?


texts: I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I have 100 to 1000 number of vertices in the tested sparse digraphs, how many times should I execute my program for a single n vertices? How do I know that the empirical differences in performance that I've obtained between data structures are not due to chance?


texts: eliminate left recursion of below grammar

texts:
Please look at this grammar:
$$ →  \  |  \   \ | \  \\
 →  \ | \   \  | \   \\
 →  \  | \ d$$
I eliminated B from the grammar and it converted to:
$$ S → SAAS \ | SAd \ | \ Ab | \ b \\
A → SAS \ | \ Sd \ | \ a \ | ASS \ | dS $$
But I can't eliminate loop recursion between A and S.Was it a good solution I removed the B at first?
How can I solve that?
any help is much appreciated.


texts:
What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round?
For example, with $N=10$ people:
$$
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \to 2, 4, 6, 8, 10 \to 4 ,8 \to 8.
$$
As you can see in the above example the killing starts from position $1$.
I was just curious to find out what would be the solution to this variant. I tried out different values of $n$ but could not find a proper algorithm.


texts: Generalization of Functors to other datatypes?

texts:
Functors in category theory, and also in its application to functional programming, can be seen as a kind of "structured" functions: Given two sets $A,B$, rather than just having a function $f:A\to B$, we have a functor $F$ which contains $f$, but additionally also maps morphisms on $A$ to morphisms on $B$ (i.e. maps not only $A$ to $B$ but also maps "structure on $A$" to "structure on $B$").

In the category theory of functional programming, objects $A,B$ are types and morphisms are functions $A\to B$ between types. That means functors map types $A,B$ to other types $X,Y$ and map functions $A\to B$ to functions $X\to Y$. Functors in functional programming can thus be seen as a mapping between datatypes that additionally also maps the functional structure on those data types.

My thought was: In the context of object-oriented programming, there really are more kinds of structure on datatypes than just functions between them. For example, given two types $Int$ and $Bool$, we can not only define functions $f:Int\to Bool$, but also things like $p:Int\times Bool$, or more complex datatypes like classes with private component classes.

Is there a generalization of functors to "mappings between datatypes that also preserve structure", where that doesn't need to be functorial? In particular I'm wondering whether such a concept is used in analyzing programming languages.


texts: Termination of Moore's algorithm to minimize deterministic automata

texts:
I use Moore's algorithm to minimize DFA as concluded below.

We start with the complete graph with vertices Q and edges E = { {p, q} | p = q ∈ Q }
We mark all edges {p, q} ∈ E with p ∈ F and q ∈ F
As long as there exist marked edges in E, we repeat the following procedure. We choose some marked edge {p , q } ∈ E. Then we mark all unmarked edges {p, q} ∈ E with {p , q } = {p · a, q · a} for some a ∈ Σ. Afterwards we remove the edge {p , q } from E.
All marked edges are eventually removed.

Then I guess a new minimal automata is obtained by joining the states linked by the remaining unmarked edges. Is it true?

If so, what about this case?

States: {1, 2, 3}
Alphabet: {a, b}
Start: 1
Final: {3}
Transition: {(1, a, 2), (2, b, 3)}

By Moore's algorithm, at the end of loop we will have one unmarked edge between state 1 and 2.
As my guess above, the next step is joining both states.
But the result doesn't make sense.


texts: Does using micro-operations require a higher clock rate than listed

texts: Say we have a modern (Skylake, say) Intel CPU running at a fixed 5GHz clock rate. Since Intel CPUs run micro-operations internally and reaches > 1 instructions per cycle, it needs to be able to run more than one micro-operation per cycle. But from how registers work we know that new data can only be stored and computation allowed to proceed at certain points of each clock cycle (e.g. the rising edge). Since the CPU internally does more than 1 micro-operation in sequence within a single clock cycle, doesn't that mean it would also need to have more than one internal clock cycle per "external" clock cycle, and hence an internal clock rate that is higher than the listed 5GHz?


texts: Any common problems solvable by DFA/NFA or PDA except recognizing languages?

texts:
I understand that DFAs recognize regular languages, and PDAs context-free languages, but these are a little bit too theoretical. I am wondering if we can implement common functions or solve common problems with DFAs and PDAs instead of Turing machines (or in a Turing-complete language).

By "common", I mean either one of the following:

problems like those in algorithm analysis and data structures, i.e. sorting, shortest path, etc.
functions seen in the everyday work of a common programmer, probably some useful business logic.


texts: When does a Monte Carlo algorithm solve a problem?

texts:
When can we say that a Monte Carlo algorithm solves a problem?

To quote from Wikipedia on Monte Carlo algorithms

  For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least ½ and true with probability less than ½.

What would happen if the Solovay–Strassen Test would answer true for only 1% of composite inputs?

Would we then still say that it solves the problem of testing primality?

Or is there some requirement like that a Monte Carlo algorithm has to answer true for more than half the cases?


texts: Closure of regular languages are closed under certain cut operations

texts:
Let $f : \mathbb{N} \to \mathbb{N}$ be an integer function. For a language $L$, define

$$f(L) = \{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\}$$

For example, if $f(n) = n$ this is just the "halving" operation, and regular languages are well known to be closed under this -- just simultaneously walk forwards and backwards (where the backwards walk tries all possible paths, like in the subset construction).

According to HMU, regular languages are also closed under taking the functions $2n, n^2, 2^n$. It is easy to see for $2n$, or any linear function for that matter - just walked backwards with whatever the speed. How can this be done for $n^2$ or $2^n$? It doesn't seem feasible to just increase the speed, since that would require remembering the number of steps taken so far.

Also, can we adapt the solution to get some general sufficient conditions on which $f$ has this property? (I doubt there are necessary and sufficient conditions, but would love to be proved wrong)


texts: Is there a unit of measurement that can express code execution speed in absolute terms?

texts:
I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware performance, and asymptotic analysis can tell us how code will perform relative to the size of the input, but they're not absolute terms.

For space performance, we have asymptotic analysis, but we can also measure performance in bytes, which allows us to express (and predict) space performance in both relative and absolute terms. e.g. algorithm X's space complexity is O(n) or n * 32 bytes of memory for implementation Y in language Z.

For example we can look at this code:

for i in n:
    pass

And if we know this will be executed using a 64-bit build of CPython, we can say this for loop will take up 72 + n * 8 bytes for the integer array and 8 bytes for each reference (independent of context/overhead).

My question is: Is there a unit of measurement we can use to express a piece of code's execution speed (or CPU usage) in absolute terms, similar to how we can with bytes for memory?


texts: Let me know about ANFIS premise prameters

texts:
I wanna ask about Adaptive Neuro Fuzzy Inference System (ANFIS) method. I used clustering to find fuzzy rules and used the mean and deviation standard of each cluster for initialization of the first premise parameters (c and a) of membership function. c is from the mean, and a is from the deviation standard

Now, my problem is I find that there's a cluster that have deviation standard = 0 (zero),  so it can't be premise parameter (where the deviation standard will be "a" parameter of membership function) because it will the gbell membership function undefined.

If a=0, how can I calculated the gbell membership function of ANFIS?
Is there any solution of finding rules and membership function of ANFIS that could be implemented in clustering?
Because I have to make ANFIS manual and I was banned to use MATLAB and I should make ANFIS in java programming and I have to do the manual first.

Thank you.


texts: Mutual Information in a Binary Erasure Channel

texts:
Imagine a Binary Erasure Channel as depicted on Wikipedia.

One equation describing the mutual information is:

$$
\begin{align*}I(x;y)
 &= H(x) - H(x|y) \\
 &= H(x) - p(y=0) \cdot 0 - p(y=?) \cdot H(x) -p(y=1)\cdot 0\end{align*}$$

Why is it "$p(y=?) \cdot H(x)$" and not "$p(y=?) \cdot H(x|y=?)$"?


texts: How good are current AI researchers at simulating complex, first-person emotional states?

texts:
I just read that IBM's Watson would have a hard time answering questions like "tell me about your first kiss." If you asked a modern, state-of-the-art chatbot questions like "tell me about a song that means a lot to you and why" or "tell me about a time when you felt vulnerable" would the chatbot be able to answer in ways that would fool non-experts into thinking that it was human? Are questions like this good candidates for the Turing test?

I am not asking a philosophical question about if it is POSSIBLE to generate an AI that could represent a complex internal emotional state. I am asking: given the state-of-the-art research in 2013: how close are current researchers to generating AI that could pass the Turing test?


texts: Constructing PDA to accept language $\{a^ib^j \mid 0 \leq j \leq 2i\}$

texts:
How can I construct a PDA which accepts the language
$\{a^ib^j \mid 0 \leq j \leq 2i\}$?


texts:
I recently found a question asking whether the language given below is context-free or not:

$L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$

My intuition is that I can design a non-deterministic push-down automaton for the language. I would appreciate if you could correct me if I am wrong, or brief me on how I could prove that it is indeed context-free.


texts:
As part of a solution to an earlier question, I am interested in the following problem.

I have a 2-D matrix $M$. I want to preprocess it in linear time so that I can answer queries of the following form in constant time:

  Given $i_1 \leq i_2$ and $j_1 \leq j_2$, what is the minimum of $\{ M_{ij} : i_1 \leq i \leq i_2, j_1 \leq j \leq j_2 \}$?

Such a method is described in On Space Efficient Two Dimensional Range
Minimum Data Structures, but I am unable to understand it.


texts:
In my uni lecture, I am covering address decoding. I understand that memory addresses are decoded to find if they point to the RAM, ROM, or I/O, by way of the address (in the example of BBC Micro) being in the RAM range, user ROM range or OS ROM range (e.g. 0x0000 to 0x7FFF is the range of RAM in the address space).
Addresses can be decoded as little as possible, that is, the minimum number of bits in the address are checked to determine the chip select signal, the signal which determines which chip to access. This approach allows for 'address shadows'. Now I'm not sure what this means, I'm repeating my lecturer.
What I understand address shadows to be are addresses which will point to the same place in memory as another, but only because we are decoding the address as little as possible.
The example my professor gave is of the original Apple Macintosh. The SCC READ chip had addresses from 90000 to A0000, but it only had 4 or 5 registers. This meant the same registers were repeated in memory, which is what an address shadow or mirror is.
Could someone expand on or correct this definition, because web searches have not turned up much fruitful information.
Thanks


texts: Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties

texts:
What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties:

thing1 (instance of "Mammal", but we don't know this now)
  -eatsFood
  -reproduces
  -hasMilk

thing2 (instance of "Emu", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -doesNotFly

thing3 (instance of "Eagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing4 (another instance of "Eagle", we just know it has the same "shape" as thing 3)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing5 (instance of "BaldEagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies
  -hasWhiteHead

And return as an output a hierarchical class structure/inheritance tree/taxonomy like the following?

Notes:

The algorithm is able to identify a hierarchical structure in the
objects' properties, including abstract classes that are not explicitly present as objects in our data set.  For example, there are no instances of "Bird" or "Animal" in our object data set, however the algorithm is able to identify that "Eagle" and "Emu" both inherit from a common parent class (the abstract class "Bird") and that both the "Bird" and "Mammal" classes inherit from a common parent class (the abstract class "Animal").
The algorithm doesn't know or care about the class names ("Animal", "Mammal", "Bird", "Emu", "Eagle", "Bald Eagle").  We generate those ourselves based on the properties of the classes the algorithm has generated.  I just put them here to aid the example, but they're not part of the algorithm.
The list of an object's properties in the data set will not necessarily be "in order" like they are here.  Don't assume any order to the properties in the raw data.


texts: Bytes from integer using bitwise operators

texts:
So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this...

int i = 512;
i & 0xFF; // this gives me the first byte

That must mean i & 0xFF gives me the first byte that is stored in memory. In other words, i & 0xFF is the first of the four bytes i consists of stored at the lowest memory address. Next, I think that i << 8 & 0xFF will then shift everything left by 8 bits and giving me the second byte. However, it is actually the opposite and only i >> 8 & 0xFF gives me the next byte. I do not understand why this is true. To me, it makes the most sense to left shift to get the next byte so why do I need to right shift by 8 to get the proceeding byte?


texts: Creating a one-to-one mapping between a N-length list and M workers?

texts:
I have a list of length N, and I have M workers.  I want each of my workers to independently select a contiguous section of the list, with the property that every element of my list is selected by exactly one worker.

Using the SQL notion of offset and limit, I have an approximation:

offset = (worker_number / total_workers * list_length).to_i
limit = list_length / total_workers + 1

The problem is that, for some values of N and M, this results in overlaps, where some elements are processed multiple times.

Is there a general solution that ensures the one-to-one correspondence between elements and workers, yet allows each worker to independently compute their offset and limit?


texts: Question regarding the Dynamic Programming solution for Rod Cutting Problem?

texts:
As per the book "Introduction to Algorithms" , to solve the rod cutting problem for a given length n, we basically iterate over all possible lengths of the first part , and calculate the optimal profit for the remaining part ( either through recursion or via stored values in array ). The profit for the first part is picked directly from the given profit array i.e. the length of the first part is taken to be as it is and not divided.
Shouldn't we also consider the optimal cost for the first part ? Isn't the idea of making one part indivisble wrong ?


texts: Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point

texts:
You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point.

One solution would be for each query to scan through every interval and see if it is contained in this interval or not, this would give us O(amountOfQueries*n) time.

I'm not sure how you would achieve better bounds for these queries with interval trees. In these trees every node is an interval but it also contains the maximum end point of the set of all intervals in the right sub tree.

If for each query you decide to search for all intervals that contain it in this interval tree, then you can still get the O(n) time if all intervals contain this point.

So, how can interval trees help in this case?


texts: How to prove finding two paths that are at least k edges apart is NP-hard?

texts:
Let $G=(V, E)$ be an unweighted, undirected, and connected graph. Given two start vertices $s_1$ and $s_2$ and two end vertices $t_1$ and $t_2$ is there a path from $s_1$ to $t_1$ and $s_2$ to $t_2$ such that the closest number of edges between the two paths is at least $k$? Two paths are $k$ close if the minimum of the shortest distances between any vertex on the first path to any vertex on the second path is $k$.

I was thinking of reducing from 3SAT and letting the first path represent the variables and the second path represent the clauses, but I am unsure where to go from there.


texts:
would be really thankful if someone could clear this up.

In reinforcement learning, When we use basis like the fourier or say polynomial basis, and say we have 4 actions, theta will then be a N x4 dimensional vector, where we dedicated each column to each action right..so q(s,a) would be theta[:,a]*feature(s)
how would we do this if we try a policy gradient approach?

So we use softmax, we still can use features independent of the actions, how do we satisy the compatability conditions in an actor critic settings? Say actor is softmax, does critic =w.T * phi(s) work ok?


texts: Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

texts:
Assumptions:

given a graph with N nodes, and two specific nodes A and B
the  graph is undirected and no edge has a negative cost
there exists at least one Hamiltonian path with A and B as an end points

Is there a way to find the shortest path from A to B that passes through all the other points?

Note: I'm only concerned with the specific given nodes A and B as endpoints, thus there's no need to compute for other Hamiltonian paths with different endpoints.

I'm thinking if it's possible to modify Dijkstra's shortest path algorithm to find Hamiltonian paths. Is it possible? If so, how? If not, is there any other algorithm that can be used? (in polynomial time)


texts: How to prove that a problem can't be solved in time $\mathcal O(n^{1/2 - \epsilon})$?

texts:
I have seen many problems in graph theory and in other related fields which admit a sublinear (in input size) running time $\mathcal O(n^{1/2})$ algorithm, where $n$ is the input size.  I am not sure but to me it seems that fine grained complexity may be one possibility to prove that there is no algorithm with running time $\mathcal O(n^{1/2 - \epsilon})$, where $\epsilon$ is greater than 0. The model of computation is RAM.

Question : How to prove that a problem can't be solved in running time  $\mathcal O(n^{1/2 - \epsilon})$?


texts: Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?

texts:
Say language $L$ is recursively enumerable, but not recursive.
Say $a$ and $b$ are symbols of the alphabet and $w$ a word.
Say we have the following language:

$L' = \{ aw | w \in L \} \cup \{ bw | w \notin L \}$

That is, $L'$ consists of the words that are in $L$ with an $a$ added at the beginning and the words that are not in $L$ with a $b$ at the beginning.

Is $L'$ not recursive? If we had a Turing Machine $TM$ for $L'$, $TM$ would halt for some positive cases ($w \in L$) but for other positive cases ($w \notin L$) it wouldn't halt. Is it therefore not recursive and recursively enumerable?

From what I understand:

Recursively enumerable: the Turing Machine will always halt if $w \in L$, otherwise it may or not halt.
Recursive: it always halts.
Recursively enumerable, but not recursive: it only halts if $w \in L$; otherwise it loops.
Not recursively enumerable: no Turing Machine exists.

So I don't know how to classify a language whose Turing Machine halts for some of its words.

EDIT: of course, now that I think about it, if the $TM$ doesn't halt and accept for some words then they didn't belong to the language in the first place.


texts: Is "backward substitution" and "backtracking" the same thing?

texts:
From my limited knowledge, they both are related to solving recurrence relation.
Solving recurrence relation using backward substitution
Solving recurrence relation using backtracking

Can the terms be used interchangeably?

In terms of algorithm, I found the following:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. wiki

Backward substitution is a procedure of solving a system of linear algebraic equations Ux=y, where U is an upper triangular matrix whose diagonal elements are not equal to zero. The matrix U can be a factor of another matrix A in its decomposition (or factorization) LU, where L is a lower triangular matrix. This decomposition can be obtained by many methods (for example, the Gaussian elimination method with or without pivoting, the Gaussian compact scheme, the Cholesky decomposition, etc.). Here we also should mention the QR decomposition when the matrix A is represented in the form A=QR, where Q is an orthogonal matrix and R is an upper triangular matrix. Since the matrix U is triangular, a procedure of solving a linear system with the matrix U is a modification of the general substitution method and can be written using simple formulas.
A similar procedure of solving a linear system with a lower triangular matrix is called the forward substitution. Note that the backward substitution discussed here can be considered as a part of the backward Gaussian elimination in the Gaussian elimination method for solving linear systems.
There exists a similar method called the backward substitution with normalization. The scheme of this modification is more complex, since a number of special operations are performed to reduce the effect of round-off errors on the results. algowiki

Are backward substitution and backtracking the same in terms of
recurrence relation?

Is backtracking algorithm is the same as the recurrence relation's backtracking?

Is backward substitution (same as back substitution?) in recurrence relation the same with backward substitution algorithm?

Is backtracking algorithm the same as backward substitution?

What are their relations to each other?
backtracking (recurrence relation) - backtracking (algorithm) - backward substitution(recurrence relation) - backward substitution(algorithm)

Can the terms be used interchangeably?


texts: How to show that a turtle graphic language is not regular?

texts:
I have to prove with the pumping lemma that $L$ is not regular or to give a regular expression for that.

Let $L$ be all combinations of commands such that in the complete drawn result no line is drawn above another. At the starting point the pen is down.

The turtle graphic is created by the following commands:

u - pen up
d - pen down
g - go
l - move 10° left
r - move 10° right

I think think that the language is not regular because I think there is an expression that crosses a line for a big enough $n \in \mathbb N$.

Question: How can I find an expression that helps me to prove that this language is not regular to use the pumping lemma?

And if the language is regular, what technique should I use to find a regular expression?


texts:
Is there an example of a timed automaton that requires infinite clock precision, in order to be controller so as to avoid a deadlock or bad state?

I.e. a transition system that consists of nodes connected by edges, and one or more real-values clocks. Nodes can be attributed with invariant (inequation on clock(s)), and edges (transitions) with guards (idem), labels, and the instruction to reset one or more clocks to 0.
The initial state is at one node, with all clocks set to zero. The controller must take transitions along the edges whose guard is valid, such that it is always at a node (location) whose invariant is valid, while the clock values simultaneously increase. I

The system should such that the controller would have to change locations faster and faster, i.e. with the difference in clock values between transitions converging to zero.


texts: how to identify patterns in program execution flows?

texts:
Consider a library, that is used by different programs. Under certain (unknown) circumstances, an error can occur. I want to feed execution traces of faulty programs to some kind of an algorithm / framework so it learns about the "pattern" which led to the error. It should then, when fed a live trace, detect when that error will occur and halt the program execution.

So what I have is a list of totally ordered invocations of library functions with their parameters and return value. A simple fault program, where a memory area is used after being freed, may look like

mylib_allocate()=0x100
mylib_dosomething() // unrelated "noise"
mylib_free(0x100)
mylib_dosomething() // unrelated "noise"
mylib_set(0x100, 0); // error here

So my question is: Are there any existing frameworks that could be fed with that kind of data, which tries to automatically identify patterns from many traces leading to the same error (e.g. "use after free"), and which produces some output which could be used to detect the error (i.e. trigger an event if such an error is going to happen)?

I looked through some data mining approaches, but it seems like they all target "manual" analysis for pattern identification, e.g. by graphic processing to visualize potential "cluster". Then I tried to look at "process mining", but this seemed to be a dead-end as well, because - as far as I understand - my invocation data with an arbitary amount of parameters doesn't fit into that "process" schema. At least I didn't get any reasonable results with ProM.


texts: How does dynamic programming work in this example(generating the tables )

texts:
For example, a sequence has the defined growth property: if it is a
  sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such
  that:

  $a_{1}=1.$
  $a_{n+1} \leq$ Max$_{1\leq i \leq n}$ ($a_{i}+1$)

  We can quickly compute the number of such sequences of length n with the power of dynamic programing:

  Let sequence(l, m)  be the number of possible sequences with length
  l and maximum number in the sequence m. The total number of such
  sequences for a length can be calculated by summing all the sequences
  with maximum value ranging from 1 to n for length l. The recurrence
  can be described as:

  sequence(l,m) = sequence(l-1, m-1 ) + m * sequence(l-1,m);

  (sequence (l,1)=1, sequence(l,m)=0 if l< m)

  As we create a table of size l * m, where we fill the matrix column
  by column. The base case: the first column of the table sequence(l, 1)
  = 1 and for the subproblems where l < m the number of sequences will be 0 since the maximum element in sequence can't be bigger than the
  length of sequence. We can now fill the table in the second column and
  apply the recurrence relation for every cell and obtain the value fro
  all combinations of l and m. Finally, We can sum up the last row to
  calculate the number of sequences.

Understand that the text already gives hint for creating the table.
but I am still struggling to visualize it. First of all,  What exactly is this sequence?

$a_{2} = a_{1+1} \leq max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq  max(2)$

and $a_{3}\leq max(3)$ but what are some example of such sequence ?
Any more guidance for completing the table?

What is exactly m in sequence(l, m)?  Where should we place $a_{4}$ in the table of l * m?


texts: Proof for Iterative Solution of Towers of Hanoi

texts:
1. Calculate the total number of moves required i.e. "pow(2, n)- 1".
       Here n is number of disks.
    2. If number of disks (i.e. n) is even then interchange destination
       pole and auxiliary pole.
    3. for i = 1 to total number of moves:
         if i%3 == 1:
        legal movement of top disk between source pole and
            destination pole
         if i%3 == 2:
        legal movement top disk between source pole and
            auxiliary pole
         if i%3 == 0:
            legal movement top disk between auxiliary pole
            and destination pole

This is an iterative solution to the Towers of Hanoi problem. I tried to prove this algorithm through some ways such as:

Induction on the number of disks(n) for both the odd and even case:
Show correctness for the base case, make the inductive hypothesis
for some n=k and then prove that it is valid when n=k+2. This would
require us to show that the remaining pow(2,k+2)-pow(2,k)=3*pow(2,k)steps of
the algorithm give the correct output for the case n=k+2.However, the number of steps in the inductive extension depends on the parameter k and is itself 3 times more than that in the base case
Induction on the number of iterations in the for loop.I tried to
    show that if disc movements for some k,k+1 and k+2 iterations occur as stated
    by the algorithm, then the k+3 iteration should execute the same condition as was executed by the k+1 iteration. However, proving by this method seemed long and tedious as the kth iteration can satisfy the first, second or the third condition and we need to prove for both the odd and the even case.

Could you help me out in proving this iterative solution to the Towers of Hanoi problem?


texts: Nearest neighbor search in latitude/longitude coordinates

texts:
I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree, but as far as I can tell, quadtrees and k-d trees are confined to working in Euclidean space. How can I efficiently do a nearest-neighbor lookup in spherical space?
One solution I've considered is projection into 3d space and then using an octree, but I'd prefer not to do that if a space-partitioning tree (or alternative algorithm) that works with spherical coordinates directly exists.


texts:
I have the following language:

{0m1n0n1m | m,n ≠ 0}

I was wanting to write Context-free grammar for it. I'm a little confused
because the rule doesn't mention that m and n are not equal to each other, so could we treat them in a case as the same?

So could something like

S --> 0S1S0S1S

or

S --> 0101 | 0S10S1 | ε


texts:
Please correct my statement.
Assuming $L\in NP$, and algorithm A can determine L in poly-time in a nondeterministic machine, we have algorithm $A'$ and the complement of $L$ -- $L'$. $x$ is the input of $A'$

A'(x)
{
   if(A(x) is true)
      return false
   else
      return true
}

In this code, it seems like $A'$ can also run in a nondeterministic machine in poly-time. Can I just say $co-NP=NP$??

Or my flaw is that the input $x\in L'$ but $x\notin L$?

Could you please give me a specific example??


texts: Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

texts:
I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1}  = app \quad \& \quad r(j) \leq p $ and (3) $t_{i-1} = app \quad \& \quad r(j) > p$. However, for two of them I can go to two directions.

To explain more, suppose I have job $−1$ scheduled. Then, if $_{−1}=$, I can schedule the next job (job $$) with two conditions: (1): start it immediately after job $−1$ is finished, i.e. at point $_{−1}$ or (2): start it two time slots earlier than job $−1$ is finished, i.e. at $_{−1}−2$. Both directions should be checked in the DP.

The formula is shown in the following, that is simplified to avoid misleading. In fact, cases 1 and 2 are the same, but can go into two directions ''app'' and ''int''. The same is for cases 3 and 4. But case 5 has only one option that is ''app''. I think the current format of the formula is missing something since the condition for cases 1 and 2, and for cases 3 and 4, is the same. What is the correct form of interpreting this formula?

\begin{equation}
z_i = \begin{cases}
z_{i-1} + p + (app) & \text{if $t_{i-1} = int$}\\
z_{i-1} + p+ (int) & \text{if $t_{i-1} = int$}\\
z_{i-1} + 2p + (app) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p\\
z_{i-1} + 2p + (int) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p\\
z_{i-1} + r(j) + (app) &\text{if $t_{i-1} = app$} \quad \& \quad r(j) > p \\
\end{cases}
\end{equation}

One thing that comes to my mind is to write it with two $\min$ functions. Since from the three conditions with $(app)$ (i.e. conditions 1, 3 and 5) one with lower objective function will be remained, and the same for the two with $(int)$ option (i.e. conditions 2 and 4). How about writing with two $\min$ functions with distinct condition for each?! For example:
\begin{equation}
z_i = \begin{cases}
\min\begin{cases} z_{i-1} + p + (app) & \text{if $t_{i-1} = int$} \\ z_{i-1} + 2p + (app) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p \\ z_{i-1} + r(j) + (app) &\text{if $t_{i-1} = app$} \quad \& \quad r(j) > p\end{cases} \\
\min\begin{cases}z_{i-1} + p+ (int) & \text{if $t_{i-1} = int$} \\
z_{i-1} + 2p + (int) & \text{if $t_{i-1} = app$} \quad \& \quad r(j) \leqslant p \end{cases}\\
\end{cases}
\end{equation}


texts: Given a minimum vertex cover can we find all the others in polynomial time?

texts:
Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem NP-complete as well?

Another question: what other ways (not necessarily polynomial-time) of finding the other MVCs when having one of them are there, Other than backtracking or re-running the algorithm that found the first MVC? A good answer to my original question would suffice marking it as such.


texts: Proving NP-completeness of an extension in List Coloring Problem

texts:
In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list
of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $c$ such that $c(v) \in L(v)$ for all $v \in V$ and $c(i) \neq c(j)$ for all $<i,j> \in E$. If such a coloring exists, we say that $G$ is $L$-colorable and that $c$ is an $L$-coloring of $G$.

In my problem: Given a graph $G(V,E)$ an integer $k$, for tractability, we take over the coloring using natural number from 1 to k. Each vertex is required to be colored by an exact number, and each vertex has different weights corresponding to its permissible colors (numbers). The objective is to minimize the sum of the weights of $v \in V$ while satisfying no any two adjacent vertices are colored using same number.

I want to prove the above problem (called P1) is $\mathcal{NP}$-complete.

Answer: Reduce the $L$-coloring List Coloring Problem to P1.

I now define a decision version problem (called P2): Given an undirected graph $G(V,E)$ and an integer $k$ in the List Coloring Problem, we ask whether a $k$-coloring can be found in $G$.

In my opinion, to solve P1, we have to solve P2 firstly and then find the minimum sum from the feasible solutions set. Since LCP is a generalization of graph coloring problem(GCP), i.e., the latter is a special case of the former, and it is well known that the $k$-coloring problem in GCP is $\mathcal{NP}$-complete. Thus, we can say that the $k$-coloring problem in LCP is also $\mathcal{NP}$-complete, i.e., P2 is $\mathcal{NP}$-complete. This concludes that P1 is also $\mathcal{NP}$-complete. Is this reduction correct?

I would sincerely appreciate if someone can give any useful suggestions!


texts: Polynomial time solution for bipartite matching

texts:
Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem:

  Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all items labelled alphabetically. Each item has a disallow list: there are certain boxes that item cannot be put into. Generate a mapping of items to boxes that does not violate any item's disallow list.

For bonus points, I would be interested in being able to generate all such mappings.

At first blush, the problem appears to be the inverse of the stable marriage problem, in that everyone has a strict list (rather than an ordinal ranking) of whom they don't want to get married to but will settle for anyone else (and strictly speaking the men/boxes have no preferences). Edit: it appears this problem is closer to bipartite matching.

A very naive solution is to simply generate all permutations and check which ones don't violate any disallow lists, but this grows as $O(n!)$. Are there any polynomial time solutions out there?


texts:
A Knowledge Proof is a mechanism by which a 'prover' entity can show to a 'verifier' entity that it possesses some certain information without revealing what that specific information is (within some arbitrarily small tolerance of certainty).
Is it possible for a 'prover' to show to a 'verifier' that it does not possess some certain information (without the 'prover' being computationally limited, etc.)?


texts:
Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.

  You are given $n$ balls on the table and all the balls are rolling towards the one end of the table with velocities $V_1, V_2, \dots, V_n$ and there is a bucket placed at that end. The distance of the ball with velocity $V_i$ from the end of the table where the bucket is placed is $D_i$. It is given that when two balls collide, both balls merge into each other and move with the velocity of the ball nearer to the bucket. So, at last, you have two tell the number of the balls which will fall into the bucket.

Here is what I am doing. First, I insert one extra ball in the array with zero velocity and distance zero. That is, I am inserting the bucket as a ball. We will find how many balls are getting merged with last ball.

Find a pair of adjacent balls which have the smallest value of
$T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$  and $V_i > V_{i+1}$ and remove ball with velocity $V_i$, that is, the first ball in the pair.
Now for each remaining ball, reduce its distance by its velocity times $T$,
and continue doing this process.

The number of time we will choose the bucket as the second ballwill be the final answer.

Can anyone suggest a better approach? My approach has time complexity of $O(n^2)$.


texts: How to iterate the Hardy-Ramanujan integers quickly

texts:
The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are:
$$
\begin{array}{lll}
  1 & = & 1\\
  2^1 & = & 2\\
  2^2 & = & 4\\
  2^1 \times 3^1 & = & 6\\
  2^3 & = & 8\\
  2^2 \times 3^1 & = & 12\\
  2^4 & = & 16\\
  2^3 \times 3^1 & = & 24\\
  2^1 \times 3^1 \times 5^1 & = & 30\\
  2^5 & = & 32\\
  2^2 \times 3^2 & = & 36\\
  2^4 \times 3^1 & = & 48\\
  2^2 \times 3^1 \times 5^1 & = & 60\\
  \vdots
\end{array}
$$
As you can see, the exponents don't really follow much of an order that I can see. I thought perhaps the exponents increased in some way, but we have $288 = 2^5 \times 3^2$ shortly followed by $480 = 2^5 \times 3^1 \times 5^1$.
Is there a method to iterate these integers quickly?
I can only see a simple way of listing all of them below some upper bound $u$. I find the maximum exponent for $2$ by $\lfloor \log_2(u) \rfloor$, find the maximum # of primes, and iterate all decreasing sequences of exponents $\leq \lfloor \log_2(u) \rfloor$.


texts: Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set

texts:
I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that:

$U$ contains at least two vertices, and $U \neq V$
There is at most one vertex in $V \setminus U$ connected to a vertex in $U$
There is at most one vertex in $U$ connected to a vertex in $V \setminus U$

(assuming there is such a subset).

The current algorithm I have works by recursively calling itself with one added vertex until the set has the appropriate conditions, but it's much too slow.

Is there any algorithm I could use to do this more efficiently?


texts: Dynamic Programming, Counting Independent Sets

texts:
My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But
my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to approach this. Any ideas would be great.


texts: Given a simple graph with $n$ vertices, show that you can remove all edges in $O(n\log n)$ rounds, where in each round you are allowed to remove all edges of any (single) path.


texts: The transition function of the union of regular languages

texts:
I follow Michael Sipser's book, "Introduction to the Theory of Computation".
To be specific, I am trying to understand the proof about the union of regular languages. However, I have a problem grasping how exactly the transition function is defined.
The book says that for each $(r_1, r_2) \in Q$ and each $a \in\sum$, let
$\delta((r_1, r_2),a) = (\delta_1(r_1, a), \delta_2(r_2,a))$. The problem is that I cannot understand what happens if, for example, $\delta_2(r_2,a) = \emptyset$ and $\delta_1(r_1, a) = q_1$ and I get $\delta((r_1, r_2),a) = (q_1, \emptyset)$, which does not belong to the set of all pairs of states.


texts: Is there any difference between having a fair scheduler (an adversary cannot reorder messages sent by correct processes) and having a reliable point-to-point FIFO link among processes?


texts:
HAMPATH

  Input: An undirected graph $G$ and 2 nodes $s, t$
  Question: Does G contain a Hamiltonian path from $s$ to $t$?

  HAMCYCLE

  Input: A undirected graph $G$ and a nodes $s$
  Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

add edge from t to s

if theres a hampath then the reduction shows there a hamcycle

if theres a hamcycle then clearly theres a hampath

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?


texts: Can this CFG be written into an equivalent LL(1) grammar?

texts:
I have the following CFG which I suspect cannot be rewritten to one which is LL(1):

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

I've thought about it for a while, and can't seem to make any progress. I know that the simpler grammar here can be rewritten into LL(1), but it seems like there is something different about the above grammar which prevents a rewriting in a similar style. Is it possible? If not, is there an easy way to prove that this is the case?


texts: How to consider combinatorial optimization problem with multiple objectives?

texts: I am considering a combinatorial optimization problem with two objectives. The two objectives have a trade-off between each other which means if I minimized the first objective alone it gives the worst solution to the other one and vise versa. How I should start tackling such problems and if anyone can recommend a famous combinatorial problem has the same nature I appreciate.


texts: Algorithm to traverse all unblocked $1*1$ squares in a $n*m$ grid

texts:
Given a $n*m$ grid, some $1*1$ squares are blocked(can't be entered) and some are unblocked(can be entered).

What is the algorithm which prints the shortest path, such that the path covers all unblocked $1*1$ squares in a $n*m $ grid ?

The starting point is given to be :$(startx,starty)$.

A $1*1$ square can be visited more than once, but all $1*1$ squares should be visited at least once and the length of path has to be minimized.

Path can end any where, when there are no more unvisited $1*1$ squares.

I have thought of dfs, but that doesn't seem to minimize the length of the path.


texts: Devise a backtracking algorithm to allocate $p$ projects to $s$ students

texts:
There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all students must have a project. I need to compute and display all possible ways of allocating projects to students under these constraints. Here's an example:

Input:

3 students, 2 projects

Output:

   P1      P2
   {1}     {2, 3}
   {2}     {1, 3}
   {3}     {1, 2}
   {1, 2}  {3}
   {1, 3}  {2}
   {2, 3}  {1}

In my attempts, I've thought about this as being related to the problem of partitioning the set of students into non empty subsets and then ignoring those partitions which have unacceptable length. i.e. for my example generate:

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

and ignore the first and last as well as double count the three in the middle as they can be arranged in a two ways (order matters for this problem). I'm not sure however how I would go about generating and filtering these subsets and even whether this is a decent solution for any p or s values.


texts: Finding a suitable NP-complete problem for reduction

texts:
We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a table such that every name shows up? Show that this problem is NP-complete.

I have difficulty in finding out an NP-complete problem from which it can be reduced to this problem.

I tried to reduce vertex cover and set cover problems but i was not successful. I am not sure if i am heading in the right direction.


texts:
Why do most programming languages (if not all) lack a 2-bit data type?

A boolean is a single bit with the values being either true or false.

Why is there no native, corresponding type where the values can be either true, false, neither or both? This data type can of course be constructed inside the language, but I figure there would be lots of usages for a more fundamental language support for it.

This data type would be very handy in, for instance:

gene programming (values being: A, C, G or T)
GUI programming (a checkbox that is: not checkable, unchecked, checked, or both/unknown)
testing (test result can be: not run, pass, fail or inconclusive)
quantum programming (values being: true, false, neither or both)

Is there a scientific reason to why this data type (quad, qool, qit etc.) has been excluded?


texts: Verifier for A_tm in polynomial time - how to formally prove it does not exist?

texts:
How would you formally prove the non-existance of a polynomial time verifier for $A_\mathrm{TM}$?

I mean we can't just say that in order to read a certain certificate we need more than poly-time because we need to prove it for any possible certificate. What would be the correct proof ?


texts: What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

texts:
I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M  accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard".

I haven't seen this kind of notation before and haven't found a good answer from searching. Is this a more specific form of saying NP-hard?


texts: Can the right childs of a node in an AVL tree be both balanced after an insert and need rebalancing?

texts:
I was trying to come up with a case where one would need rebalance the following case in an AVL tree:

I think that case impossible to happen during an insert. It seems to me that its impossible to get to case 2 with only inserts (might be possible with deletes) since to get to that state we need B and C to have the same height, k-1 and increase both by 1 with one single insert. That seems impossible with only 1 single insert. Does that mean that case in rebalancing an AVL tree is impossible? Or can it maybe happen when one has to propagate rebalancing back in the AVL tree?

In fact, when does that case ever happen?


texts: Can you suggest a topic for a Bachelor Thesis in Mathematics that is related to Machine Learning?

texts:
Context
I am a final year Bachelor of Mathematics student and next semester I will write my Bachelor thesis.
My interests are in Machine Learning (ML) and I will do a master in ML next year. More specific sub-fields I like are

Deep Learning
Computer Vision
Natural Language Processing
Reinforcement Learning

And my interests outside of ML and mathematics include

Self-driving cars (e.g. Tesla)
Rocket and space exploration

more vaguely, I find tech interesting as a whole.
Question
I am looking for a thesis which would bring me as close as possible to the field of ML. Do you have topic recommendations ?
BUT my Bachelor is in Mathematics therefore I shall not write a thesis in Computer Science as it would not be accepted by my study director.
Some thoughts
I know some people who were in my case. One of them for instance discovered and proved some convergence results in the context of Gradient Descent. Maybe this will inspire you with your answers.
Thanks in advance!

PS: This is a duplicate of my original question on the Math Stack Exchange but I thought that people on the Computer Science Stack Exchange could bring a different point of view.


texts:
It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice versa. I get the first half, that a red root can be changed to black at any time, but in what circumstance is it impossible to change a black node to red?

For instance, consider the branch: black--red--black--red--black. We can always change it to red--black--black--red--black, since a black node does not need to have red children.


texts: Converting non-deterministic algorithm to deterministic

texts:
I was thinking about an non-deterministic algorithm to generate all the subsets of the $\{1..n\}$ set.

Subsets(n)
    S' = null
    for i = 1..n
        u = choice(1..n)
        if u in S'
           fail
        S' = S' + u
    for_each u in S'
         print u

How would I convert this algorithm into a deterministic form? I know that it is a lot more complicated to convert the choice statement in a deterministic manner but I want to get a general idea about maybe representing it in a deterministic manner.


texts: Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

texts:
Given inorder and preorder (or postorder) traversal sequences of a

binary tree
balanced binary tree
binary search tree

of n nodes, what is the time complexity of creating the respective unique tree.


texts: Can someone give a generic definition of any Definite Language in set builder notation?

texts:
What I have come across as a definition is - a language $L ⊆ Σ^*$ is said to be definite if and only if $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$

Using these questions - Show that every definite language is accepted by a finite automaton

and What are definite languages? How do you formally define them?,

I understand that a definite language is a language where the membership of a string depends on it's last k-symbols only, i.e, those strings sharing the last k-symbols either belong to the language or don't. On these lines, I don't understand how the definition correspond to - $L = E ∪ Σ^*Η$, for some finite languages $E,H ⊆ Σ^*$.

Having an intuitive idea, I am not quite able to get my head around a generic definition of a definite language in Set Builder Form. Could you please give a definition in Set Builder Notation specifically? I also request you to explain why you have defined it in such a manner, as I don't want to be in a situation where I couldn't understand the prior definition being $L = E ∪ Σ^*Η$. I have been going at this for an entire week, now.


texts: Prove that following grammar is ambiguous; S → a | S + S | S S | S* | ( S )

texts:
Prove that the following grammar is ambiguous; S → a | S + S | S S | S* | ( S )
checking ambiguity in grammar. the subject of this question is compiler construction and automation. would you please help me find the answer we only have to figure out whether its ambiguous or not


texts: Poly-time computability of inversion of poly-time real functions

texts:
At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases:

  Let $INV_1$ be the operator that maps a one-to-one function $f:[0,1]\rightarrow [0,1]$ to its inverse function $f^{-1}$. Then $INV_1(f)$ is polynomial-time computable for all polynomial-time computable, one-to-one real functions $f$ on $[0,1]$.

And for two dimensional cases:

  Let $INV_2$ be the operator that maps a one-to-one function $f:[0,1]^2\rightarrow [0,1]^2$ to its inverse function $f^{-1}$. Then $P=NP$ implies that for all polynomial computable, one-to-one real functions $f$ on $[0,1]^2$, $INV_2(f)$ is polynomial-time computable, and this in turn implies $P=UP$.

How is the one-dimensional case derived? And how can the two-dimensional case be extended to n-dimensions?


texts:
We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it.
Can you give me intuition for why the algorithm works? And can you please explain why it is correct? Why are we sure to find negative circles?
Also, we learned the following two lemmas:

Lemma (upper bound property): At all times we have that for all $v$, $v.d \ge \delta(s,v)$.

Lemma (Path-relaxation property): Let $p = \langle s=v_1, v_2, \ldots, v_n \rangle$. Following any sequence of relaxations in which the edges $(v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k)$ are relaxed in order, we have that $v_k.d \le w(p)$.

Here:

$v.d$ is the distance of $v$ from the initial vertex $s$. (We constantly update this value using the relax function in the Bellman–Ford algorithm.)

$\delta(s,v)$ is the minimum weight path between $s$ and $v$.

$w(p)$ is the total weight of path $p$.

Can you give me an intuition for the lemmas and what they mean?


texts: Are hardware specs relevant in software performance comparisons?

texts:
I notice occasionally in blogs or articles comparing different languages, algorithms, etc. that the author will divulge info about the processor used in the testing. Is this meaningful?

Shouldn't the relative performance differences be hardware-agnostic? That is, if Language A executes in twice the time as Language B, shouldn't that roughly persist no matter the hardware?


texts: Turing recognizable language between languages that aren't recognizable?

texts:
Let $L_{1},L_{2}$ be languages that are not Turing recognizable, and let $L$ be a language such that $L_{1} \subseteq L \subseteq L_{2}$.

Is $L$ also not Turing recognizable?

I am inclined to believe it is, but I really have no idea how to show this. It seems that non-recognizable languages have very little about them that could  be used to solve a problem like this. Ideas?


texts: Why not relax only edges in Q in Dijkstra's algorithm?

texts:
Can someone tell me why almost in every book/website/paper authors use the following:

foreach vertex v in Adjacent(u)
    relax(u,v)

when relaxing the edges, instead of:

foreach vertex v in Adjacent(u)
    if (v is in Q)
        relax(u,v)

This is extremely confusing for someone when learning the algorithm. Is there any reason why the people are omitting the IF ?

Anyway I wrote a semi-Javascript (I changed it here to a readable syntax) implementation of Dijkstra and I wanted to be sure if it is correct because of this IF case. Here is my code excluding the initialising:

while (queue.length != 0)
    min = queue.getMinAndRemoveItFromQ()
    foreach v in min.adjacentVertices
        // inspect edge from "min" to "v"
        if ( queue.contains(v) AND min.priority + weight(min,v) < v.priority )
            v.priority = min.priority + weight(min,v)
            v.pre = min

Is this implementation correct or am I missing something ?


texts: Priority queue of constant size fit for extraction of K highest priority elements

texts:
In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible:

get $K$ highest priority elements (do on them some outside calculation)
append $4K$ kind-of-sorted elements back into the priority queue, removing and ignoring the first $K$ elements from step 1
remove the $3K$ lowest priority elements (in order to keep constant queue size), and return them

In reality, steps 2-3 will probably be merged somehow and so on, but these are the main implementation details.

I'm looking for the fastest implementation of these actions on a priority queue, for a relatively large $N$ and relatively small $K$ (E.G $K=32$, $N=2048$), that can be tweaked a little if needed (E.G change $N\rightarrow 2500$ if it's faster).

I'm not so familiar with data structures, but here's an assortment of things that might work:

a sorted array, using $O(1)$ extracts and $O(N)$ merges
a pairing heap? weird extract times, but $O(1)$ merges
a more exotic heap type? I've found this question for example, with priority queues that technically are quicker at extracts


texts: Why can't we mimic a dog's ability to smell COVID?

texts:
As far as I can tell, we have invented tools and algorithm to:

Detect a wider range of colors at a larger range than humans or any other animals on the planet
Detect sound with wavelengths inaccessible to humans or most animals on the planet

But why is it that dogs can smell COVID or Cancer and we can't produce a similar tool to "smell diseases"? Why can't we mimic the dog's sense of smell: is it a hardware limitation or a software one? Am I mistaken in thinking that this sense is the hardest to mimic?


texts: Analyze Speed Up in A Dispatcher-Woker Model

texts:
In a Dispatcher-Worker model of parallel computation, we have $N$ worker machines simultaneously working on the task (for example, computing the checksum of network packets). There is no synchronization between these workers. A dispatcher distributes total amount of work $S$ to these workers.

Now consider the problem of analyzing the speed up of this model. To simplify the situation, assume the dispatcher evenly distributes work $\frac{S}{N}$ to each worker. And each worker finishes it within $X_i \sim \mathcal{N}(\frac{S}{N}, \sigma^2)$ time, where $\mathcal(\mu, \sigma^2)$ is the Gaussian distribution. Then I think the mathematical formula for the total amount of time needed is
\begin{equation}
Y = \max(X_1, X_2, ..., X_N)
\end{equation}

The question is how to compute the distribution of $Y$, so that analytically we could understand the parallel time needed, in terms of the number of workers $N$.


texts: Can Tug of war problem be solved by DP or greedy approach?

texts:
For problem explanation: https://www.geeksforgeeks.org/tug-of-war/

I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ideology of the solution. Also please mention if there are exceptions to this greedy or DP solution where it may not apply.


texts: Difference between $NP\cap coNP$ and $NEXP\cap coNEXP$

texts:
$NP\cap coNP$ is low for itself: $NP^{NP\cap coNP}\cap coNP^{NP\cap coNP}=NP\cap coNP$.

Going up to exponential realm, we are considering similarities of $NP\cap coNP$ to its exponential version $NEXP\cap coNEXP$.

By padding, we already have $$NEXP^{NP\cap coNP}\cap coNEXP^{NP\cap coNP}=NEXP\cap coNEXP$$

Two questions:

Though it is unlikely, I do not know for sure whether $NEXP\cap coNEXP$ is low for itself: $$NEXP^{NEXP\cap coNEXP}\cap coNEXP^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$
Being more moderate in using oracle machine, we may ask whether $$P^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$


texts: Expected depth of modified kind of treap

texts:
If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the priorities will have duplicates, I just want the treap the verify that for each node $s_k$, all the nodes in its right and left subtrees have smaller priority.

Is there a way to find the expected depth of this tree?


texts: Why doesn't decision tree work in case find minimum

texts:
When we would like to prove lower bound comparison algorirthm, we often use decision tree, for example sorting by comparisons.
So let's consider find minimum in array $a[1..n]$  by comparison.  Lower bound for that problem is commonly known - $n-1$ comparisons.

However, how to use decison tree in order to prove lower bound ?
It seems that it might be (analogously to sorting problem):
$n$ - number of possible results (similiar to $n!$ in sorting).
So the number of comparison (minimal height of tree) is $\log_2(n) < n - 1$.

Believe me, I have tried to understand it, but I can't.


texts: Does a Haskell program count as an inductive proof?

texts:
Is the following statement from [1] true?

"Since recursion is the main computational technique, a terminating pure Haskell program counts as an inductive proof of a theorem."

My intuition is that inductive proofs require a base case, assume the hypothesis case for k, prove induction step fork+1.
I am not clear on how these steps occur in the execution of a program (function?). Also, what logic is employed in such a proof?

Regards,
Patrick Browne

[1] http://ebooks.iospress.com/volumearticle/44257

Thanks for your very helpful answers.

Would it be fair to say that the answer may be morally yes [1], but technically perhaps no [2].

Below are two Haskell programs together with what I consider to be equational proofs (not inductive) that they evaluate to a desired ground term.
The first program is not recursive. So does the quote in my original posting include non-recursive programs?

    -- Prog 1 non-recursive
x,y,z:
x = 1
y = x + 2
z = x + y
proveZ = z == 4
-- Equational Proof
[1]: (z)
---> (x + y)
[2]: (x + y)
---> (1 + y)
[3]: (1 + y)
---> (1 + (2 + x))
[4]: (1 + (2 + x))
---> (1 + (2 + 1))
[5]: (1 + (2 + 1))
---> (1 + 3)
[6]: (1 + 3)
---> (4)

-- Prog 2 recursive
data Vector  = Empty | Add Vector Int
size Empty  = 0
size (Add v d)  = 1 + (size v)
proveSize =  size (Add (Add Empty 1) 2) == 2
-- Equational Proof
[1]: (size (Add (Add Empty 1) 2))
---> (1 + (size (Add Empty 1)))
[2]: (1 + (size (Add Empty 1)))
---> (1 + (1 + (size Empty)))
[3]: (1 + (1 + (size Empty)))
---> (1 + (1 + 0))
[4]: (1 + (1 + 0))
---> (1 + 1)
[5]: (1 + 1)
---> (2)

The motivation for my original question is that I wish to understand the relationship between the evaluation of a Haskell program and the application of equational logic to the same Haskell program. While Haskell produces the correct answer, as would a non-functional language, is the computation a proof in equational logic?  I imagine that Haskell cannot do any form of symbolic proof (e.g. id a == a).
In summary is my yes/no opinion reasonable?

[1] Fast and Loose Reasoning is Morally Correct:
 http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf

[2] Formulating Haskell: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.1399


texts: Error detection and correction with "feedback functionality" against several rules in data structures

texts:
I have a complex data structure DS that needs to be checked for validity against several rules. If invalid, the DS has to be corrected. The correction with respect to one rule could result in an invalid state of DS again.

There are n rules to check the data structure. If DS is valid for
all rules, DS is valid. If DS is invalid with respect to at least
1 rule, DS is invalid.
For each rule, there is a correction algorithm that mutates DS in
a way that it becomes valid with respect to the rule.
But the correction of one rule could potentially invalidate DS with
respect to another rule.

Example:

Input: DS (data structure), r1 (rule 1), r2 (rule 2)

Function isValid(DS, r) : Checks if DS is valid with respect to rule r1

Function correct(DS, r): Mutates DS so that it is valid with respect to r

Let's assume that DS is not valid with respect to r1 but valid with respect to r2
Now we need to execute correct(DS, r1) to correct the DS.
It could now be that the correction of r1 has mutated DS in a way so that it is now invlaid with respect to r2. So we run a check: isValid(DS, r2).
If the check yields false, we need to call correct(DS, r2)
This again could mutate DS in a way so that it is now again invalid with respect to r1 ...

So we need to check all rules and correct them as long as DS is invalid with respect to any rule. This could end in an endless loop, so I introduced a guard value. If DS cannot be corrected within for example 1000 iterations, DS is considered uncorrectable.

My current algorithm to cope with that is:

anyRuleViolated = true

WHILE anyRuleViolated AND ++iteration < guard:
    anyRuleViolated = false

    FOR EACH r in Rules:
        IF isValid(DS, r) == false:
            anyRuleViolated = true
            correct(DS, r)

Under search terms like "Error detection and correction" I only find correction mechanisms without that "feedback loop" (=correction of r1 can result in the violation of r2, ...). But I can't believe I'm the first person in the world running into that problem :)

These are my questions:

What do you think about the algorithm? Does it seem legit?
Do you know the category in which this problem lies? A search term or keyword I could use to search the web or publications for further insights into that problem?


texts: Techniques (tools) to convert temporal logic (CTL,CTL* or LTL) to μ-calculus formulae

texts:
Suppose one wants to use a μ-calculus model checker, but specify things in temporal logics, which is easier (more intuitive). Is there a technique (even better, a tool) that automatically translates formulae in any of these logics (CTL,CTL* or LTL) to the μ-calculus?

Thanks very much in advance!


texts: How to get the quick answer to the "Is there AT LEAST ONE subset that contains all given elements?" question if the set of subsets is very large?

texts:
I have a very large amount of objects that look like this:

DataDict = {
id1: {"a": true, "b": true, "bc": true, "hgf": true},
id2: {"bcwe": true, "nKNNn": true, "mjj": true, "AAt": true},
id3: {"h": true, "a": true, "mjj": true, "ABwAU": true},
id4: {"wvzy": true, "zzba": true, "abc": true, "a": true},
...
}

or just (as a set of sets, note that ids may be excluded)

DataSet = {
{"a", "b", "bc", "hgf"},
{"bcwe", "nKNNn", "mjj", "AAt"},
{"h", "a", "mjj", "ABwAU"},
{"wvzy", "zzba", "abc", "a"},
...
}

Let M denote the total number of objects in DataDict (or subsets in DataSet), and let N denote the total number of unique names of properties found in DataDict (or the total number of unique strings found in DataSet).

The question is: given the set of strings {string1, string2, string3, ...}, how to get the Yes/No answer (assuming that there is a way to prepare the “index” for DataSet) to the “Does DataSet contain at least one subset that contains string1 AND string2 AND string3 AND ...?” question as fast as possible?

In another form, the question is: given the array A = [string1, string2, string3, ...], how to build the index (data structure) for DataDict that allows to quickly determine if it contains at least one object obj (I don’t care which object to choose, moreover, I don't want to return this object, all I want is that the function should return true if such an object exists, and false if not) such that DataDict.obj.string1 is true AND DataDict.obj.string2 is true AND DataDict.obj.string3 is true AND ...?

The only way that I see is to build the index like this:

{
"a": [1, 3, 4],
"abc": [4],
...
}

and, for example, if A = ["a", "abc"], then I need to find the intersection of two arrays ([1, 3, 4] and [4]), but stop as soon as one common element is found and return true (if there are no common elements, return false). But these operations are very costly and time-consuming, which often leads to the unacceptable waiting time. Is there a way that guarantees a significantly better performance for all cases?

It would be extraordinarily nice if there exists a solution that (assuming that the index already exists) finds the answers depending on A.length time. The good solutions may depend on log M or log N or even close to log M multipled by log N, but I cannot imagine how to find such a solution...


texts: Proving greedy choice property of fractional knapsack

texts:
A typical way of proving the greedy choice property of the fractional knapsack problem is as follows:

From Slide 5 of this link:

Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights $\{w_1,w_2 ... w_n\}$ and values $\{v_1,v_2 ...v_n\}$. Let $P$ be the problem of selecting items from $I$, with the weight limit $K$ such that the resulting value is maximum.

Let $O = \{o_1,o_2 ... o_j\} \subseteq I$ be the optimum solution of problem $P$.

Let $G = \{g_1,g_2 ... g_k\} \subseteq I$ be the greedy solution, where the  items are ordered according to the greedy choices.

We need to show that there exists some optimal solution $O'$ that includes the choice $g_1$
.

CASE 1: $g_1$ is non-fractional.

If $g_1$ is included in $O$, then we are done.
If $g_1$ is not included in $O$, then we arbitrarily remove $w_{g_1}$ worth of stuff from $O$ and replace it with $g_1$ to produce $O'$.
$O'$ is a solution, and it is at least as good as $O$.

In the above proof, step $3$ for CASE 1 merely shows that weight criteria is satisfied. How does it show that $O'$ is also an optimal solution(i.e. in terms of value achieved), more so when we are "arbitrarily removing $w_{g_1}$ worth of stuff" without paying attention to corresponding change in value ?

UPDATE: I found the answer in terms of change in value here. I am not sure if this should go into the answer part. Mods, please suggest.


texts: Min path cover problem in Cormen et.al. question about notation

texts:
In the book on algorithms by Cormen et.al, the problem 26-2 describes how to obtain a min-path cover for a DAG via max-flow. I have a question about the notation. First, let me quote the problem here:

A path cover of a directed graph $G = (V, E)$ is a set $P$ of vertex-disjoint paths such that every vertex in $V$ is included in exactly one path in $P$. Paths may start and end anywhere, and they may be of any length, including $0$. A minimum path cover of $G$ is a path cover containing the fewest possible paths.
a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph $G =(V, E)$ (Hint: Assuming that $V = {1, 2, ... , n}$, construct the graph $G' = (V',E')$, where:
$$V' = \{x_0,x_1,\dots x_n\} \cup \{y_0, y_1, \dots y_n\} $$
$$E'=\{(x_0,x_i):i \in V\} \cup \{(y_i,y_0) : i \in V\} \cup \{(x_i,y_i):(i,j) \in E\}$$
and run a maximum-flow algorithm.)

What are the $x_i$ and $y_i$ here? Am I missing something obvious?


texts:
I am solving a problem in the Kaggle learn section : https://www.kaggle.com/c/facial-keypoints-detection

The problem involves detecting facial keypoints in a 96x96 image, some 30 features are detected. It is a supervised dataset.

I am using a convolutional neural network with max pooling, 2 convolutional layers and 2 max pooled layers, and one fully connected layer.

The problem uses the rmse metric for scoring.
So i used an ADAM optimizer to minimize the rms loss.

CASE 1:

I just simply trained the model, i got an average training rms error of 11.2, and finally when the output is generated I clamp the values which are greater than 96 (It's a 96x96 image) to 96, i get a test rms error of 9.1.

CASE 2:

I train the model itself with the clamped output values, i.e any output of greater than 96 gets clamped to 96 while training.

I thought CASE 2 would lead to faster and better convergence.
I used the same hyper-parameters for CASE 2 and found that it is converging more slowly and gives a very high rms error of around 180.

Can anyone explain what is happening?


texts: Is every edge of a graph included in some spanning tree?

texts:
Let's say we have a graph $G$. We pick one edge from it (any edge). Will there always be such a spanning tree that contains that very edge?

I think the answer is yes, because no matter what we do we can always create such a spanning tree so that the very edge we picked is included. Of course, a more formal proof would be needed?


texts:
Can you recommend an algorithm for the following problem? If you have any suggestion for simplifying the problem I am open to it.

There is a number line going from $0$ to $x$. There are $r$ rewards and $o$ obstacles placed on the line. Items can only be placed on whole numbers. There is an animal at point 0 which can jump forward and backwards. There is an array of jump lengths for the animal, for example animal A can jump either 1,2 or 5 in any direction.

Given this information, I need an algorithm that decides if the level can be solved (that is, if all rewards can be collected without landing on any of the obstacles) and what is the least amount of jumps it takes to solve it. (We don't care about the length of the jumps.)


texts: Unique representation of 5-number sets with values 1-13

texts:
From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5.   Values can repeat but they can repeat at most 4 times (it is a deck of cards).  As it turn out there are 6175 combinations.  Calculate the value of the tuple is expensive but it is pretty cheap to just generate the tuples in value order - save that and do a dictionary lookup. Without sorting the numbers what is the smallest number to uniquely represent the 5 number combination and how to generate that number?

Right now I just raise 5 to the 0-12 power and add the 5 as a proof of concept and it works.  But that is fairly expensive and uses 32 bits.  I want to get the bits and compute down.  How might I do that?

Yes I have had few questions on this subject but I promise to make this my last.

In a related question got an answer for 5 numbers 1-52 in 27 bits using some magic numbers and XOR.  I cannot figure out how to create those magic numbers for 1-13.


texts:
I got a weighted, connected and directed graph $G$. There is a vector called the distance vector $Dv \in \mathbb{N}^n$ in which $Dv_i$ is the shortest distance from $1$ to $i$. All edge weights are positive integers. I have to show that every distance vector $Dv$ satisfies:

$Dv_1 = 0$.
For all $j \neq 1$ there exists $i$ such that $Dv_j = Dv_i + w(i,j)$.
For all $i,j$ it holds that $Dv_j \leq Dv_i + w(i,j)$.

I think that 1 is trivial: from 1 to 1 you have no distance. But the rest? Can you give me an idea how to prove 2 and 3?


texts: Task scheduling algorithm (minimize wait time)

texts:
Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once.

I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1\le t_2\le \cdots\le t_n\le 10^9$.
This list says that the $i$-th execution of task cannot be ended earlier than $t_i$.

I want to minimize following sum: $\sum_{i=1}^{n} (e_i-t_i)$ where $e_i$ tells me when the $i$-th execution of task has ended. So I want to minimize a sum of wait-times for each task execution. Example:

$n = 4$;
$p=3$;
$t=\{1,2,7,15\}$;
Answer: 8

Explanation:
We start doing first task at time 0 and we end at time 3 (wait-time so far is 2). We start doing second task at time 3 and end at time 6 (total wait-time is 6). We start doing third task at time 6 and end at time 9 (total wait-time is 8). We start doing last task at time 12 and end at time 15 (total wait-time is still 8).

I can easily calculate this sum in $O(n)$ because it's equivalent to:
$$\sum_{i=2}^{n} \max(0, e_{i-1}+p-t_i) + \max(0,p-t_1)$$
$$e_i=\max(t_i, e_{i-1} + p)$$
$$e_1=\max(t_1, p)$$
but let's say that I have $k$, $k<300000$ tasks, each task has it's own running time $p_j$ and I want for each task with running time $p_j$ calculate minimize above sum (time constraints remains the same for each $p_j$).

A naive approach would give me running time $O(nk)$. Is there a better way?


texts: Number of replicas needed for fault tolerance in state machine replication

texts: I am trying to get my head around "State Machine Replication". I understand that it is a way to ensure resilience against failures. I have read that in order to provide fault tolerance against normal failures it can be derived that, there must be 2F+1 replicas and 2F+1 replicas in the case of Byzantine failures, when messages are signed, otherwise 3F+1 replicas. This is stated at the Wikipedia page : https://en.wikipedia.org/wiki/State_machine_replication. Though it does not say anything about if these derivations are in a synchronous or asynchronous environment? Can anybody clarify the needed numbers of replicas in a synchronous and an asynchronous enviroment in order for a distributed system to be fault tolerant?


texts: Does there always exist a reduction between two NP-hard problems?

texts:
Let $A$ and $B$ be NP-hard problems. For all tuples $(A, B)$ does there exist a polynomial time reduction from $A$ to $B$ and from $B$ to $A$?

Context: I want to prove some problem is NP-hard. Can I pick any problem in NP-hard to reduce from?


texts: $FIRST_k$ set -- is algorithm given by Aho&Ullman correct?

texts:
I am writing this, because no matter how I look at the algorithm I see an error :-)

Aho & Ullman in "Theory of Parsing, vol.1" (pp. 357-359) described the algorithm for building $FIRST_k(A)$ set for any $A$ non terminal by incrementally building helper set $F_i(A)$ which has such property that every $F_i(A)$ set is contained in $F_{i+1}(A)$ and it is finally equal to $FIRST_k(A)$.

However I found a counter example for this, for $k=2$.

A := a B
B := b

$FIRST_k(A) = \{ a b \}$, while $F_0(A) = \{ a \}$.

Any help is appreciated, here is shortened content of those pages -- FIRST(k) -- and if you don’t have a book, I asked the same question in longer form as blog-post -- LALR(k) FIRST sets.


texts: Can we move quantifiers to the left in predicate logic?

texts:
Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃xa,xb,xc(...∧...∧...) - i.e. compacting all the existential quantifiers into one and 'anding' their domains together?

For example, if I have the query:

would it be correct (albeit unwieldy) to write it as:

{ xpid | ∃xpname,xcolor,xsid,xsname,xaddress,xcost,ysid,ysname,yaddress,ycost( PARTS(xpid,xpname,xcolor) ∧ SUPPLIERS(xsid,xsname,xaddress... (and then the rest of the query)


texts: Complexity of Finding Every Cycle in a Graph?

texts:
What's the best asymptotic complexity of finding every cycle in a simple, directed graph?
I haven't been able to find anything regarding this online. I'm able to use DFS for cycle detection, but I'm looking to determine the weight of each cycle in a graph, thus I'd like to be able to determine them all.


texts: DFA and equivalence classes: counting odd numbers of b's

texts:
I am studying for an exam and found an exercise about finding the equivalence classes for $L=a^*ba^*(ba^*ba^*)^*$, the language over $\{a,b\}^*$ with an odd number of b's.

We found three equivalence classes: $[a^*], [a^*ba^*(ba^*ba^*)^*], [a^*ba^*ba^*(ba^*ba^*)^*]$. This means the minimal DFA would have three states, and it was given so:

But it seemed to me that the following DFA with two states would achieve the same result (by merging q0 and q2).

This is a contradiction with having three equivalence classes.

What went wrong here, and where?


texts: Zero knowledge proof - case of graph 3-coloring (not understanding the concept)

texts:
In zero knowledge, in the context of graph 3-coloring, I do not understand how the prover is actually showing that he solved the problem.
The context:

both know the graph (the prover and the verifier)

the prover solves a 3-coloring of the graph

repeat:
*the prover randomly permutes the colors
*the verifier asks for the coloring of an edge
*if the colors are different the process continues, and the verifier is more convinced that the prover actually solved the 3-coloring, if not, the verifier knows that the prover did not solve the 3-coloring

My question is: why couldn't a false prover (someone that does not know how to solve for the coloring) just always provide 2 different random colors?


texts: Can anyone explain the pigeon-hole encoding method in proportional logic

texts:
Someone there who worked with cardinal contraindications within the framework of propositional logic? I have a problem understanding the pigeon-hole method. It is a method of satisfaction. I have been trying to understand these three patterns for several days now and I am desperate. Can anyone please explain these three formulas to me using an example?

I am also adding a link to the whole article
https://static.cambridge.org/content/id/urn:cambridge.org:id:article:S1471068413000112/resource/name/tlp2013026.pdf
I identified such an example . I also gave cardinal contains as an example
>=3 x1 x2 x3 x4 x5 x6 x7

I have about the notation correctly and probably also the formula 10, correct me if I am wrong
            p13   p14   p15   p16   p17
      p22   p23   p24   p25   p26
p31   p32   p33   p34   p35
x1    x2    x3    x4    x5    x6    x7

formula 9
-p31 V x1
-p32 V x2
-p33 V x3
-p34 V x4
-p35 V x5
-p26 V x6
-p17 V x7

-p22 V x2
-p23 V x3
-p24 V x4
-p25 V x5
-p16 V x6

-p13 V x3
-p14 V x4
-p15 V x5

formula 10
p13 V p14 V p15 V p16 V p17
p22 V p23 V p24 V p25 V p26
p31 V p32 V p33 V p34 V p35

formula 11
p31 V P22
p22 V P13

p31 V p32 V P23 V -p14
p31 V p32 V p24 V -p15

Can you check if it is correct?


texts:
https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf

Why do we use blossom contrast in maximum matching?
The examples that I have seen can easily be solved by just iteratively finding a augmenting path and complementing it. I am talking about edmond blossom algorithm.

Edit:
http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching/

this is what I was looking for in the first step we have only 13 edges and we can not find any augmenting path.

now due to bloosom contrast we have increased matching by 1 edge.