texts:
I'm currently studying compiler construction book "Compilers Principles, Techniques, and Tools (2nd Edition)" , in page unit 3.1 , page 113 , example 3.2 .

i cannot understand what is this kind of method ?

  E = m * 2;

  conversion to token types(this method) below

<id , E> <op=> <id , m> <op*> <number , 2> <op;>

it is token-type pairs ? or is there any technical term associated ?


texts:
This is a question based on this one

I've also tried this problem but I can't seem to understand Henry's solution to it.

Why is the average distance between the sticks $(n+1) / (k+1)$ and not $n/ k$


texts: Are there codes that detect the position of an error?

texts:
I am looking for code that detect an error and it's position (or an aproximation of it), this is more than an error detector code but a little less than a correcting code.

Do you know something like this or some literature that I can check?


texts: How does a computer interpret real numbers?

texts:
I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers.

But I want to know how does the present day computational model interpret real numbers.

For eg:

  On a daily basis we can see that a computer can plot graphs. But here, graphs may be continuous entities. What is the
  mathematical basis, that transforms a discrete (or countable, at most)
  like the binary system to something mathematically continuous like a
  say, the graph of $f(x) = x$.


texts: Graph add at most 2 edges to make all graph nodes degree even

texts:
Given an undirected graph that is represented by its adjacency matrix, return whether or not is it possible to add no more than two edges to this graph in order to make all the degrees of nodes even. Keep in mind that in the resulting graph there should be at most one edge between any pair of nodes.
For
graph = [[false, true, false, false],
         [true, false, true, false],
         [false, true, false, true],
         [false, false, true, false]]

the output should be true.
This is my proposed broken solution:
boolean addEven(boolean[][] graph) {
    int odd = 0;
    int even = 0;
    for (int i = 0; i<graph.length; i++) {
        int k = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                k++;
            }
        }
        if (k%2==1) {
            if (k == graph[0].length-1) {
                return false;
            }
            odd++;
        } else {
            even++;
        }
    }
    if (odd == 2 && even == 3) {
        return false;
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd <=4) {
        return true;
    } else {
        return false;
    }
}


texts: Advice needed. NLP and ML. Where to start?

texts:
Hi fellow computer scientists,

I just began my journey to the world of ML and NLP so please bear with me. I'm hoping to find some guidance here. I would be very grateful if anyone could point me in the right direction (reading materials, lectures, specific algorithms, tools, etc.) for solving the following list of problems:

Spell checking, grammar checking, proofreading with ML
Text generation on a given topic with ML
"Artistic Style Transfer" for articles (if it is even possible), i.e. "transfer" Shakespeare's writing style onto a given text.

I've done some learning already but neither of this helps:

ML lectures by Andrew Ng
Hacker's guide to Machine learning
Udacity's Introduction to Deep Learning


texts: Which Data Structure should I use to store words from a novel?

texts:
So, I was learning Data Structures in Java on my own. And there was a "challenge question" in the book.
The question basically asked me to make a data structure that could store all the words in a novel, and then it would associate with the word, where it occurs (like line number and character count) and the frequency of the amount of times it occurs.
I was wondering which data structure should I use to store all this while maintaining a relatively Fast look up time and such.

I was thinking either hashmaps or tries, but I don't know which trie to use and how to associate the frequency of the word and stuff

Thanks in advance!


texts: Terminology for property of recursion definitions

texts:
I have a question about generally accepted terminology (and whether it exists at all).

Some recursive algorithms on hierarchical data structures (trees) have the property that they are expressed as a function which does a single recursive function call on each of its children, and that this call takes no parameters other than the child node.

Example in Python:

def sum_of_values(node):
    result = node.value
    for child in node.children:
        result += sum_of_values(child)
    return result

Other algorithms do not have this property, and fundamentally cannot have this property.

Consider, for example, a mechanism for pretty-printing an AST, which has the property that we want the first child of any node to be displayed on a single line, but all the other nodes on their own line.

Also sketched in Python, leaving out many details (e.g. indentation):

def pretty_print(node, single_line_mode=False):
    if single_line_mode:
        return "(" + " ".join([pretty_print(child, True) for child in node.children]) + ")"

    result = "("
    if len(node.children) >= 1:
        result += pretty_print(node.children[0], True)

    for child in node.children[1:]:
        result += "\n" + pretty_print(child, False)

    result += ")"
    return result

The key point of the above is: The recursive call contains more information than simply the fact that some work must be done recursively. This information flows from the structure higher up in the tree (in this case: whether the some node in the path of presently printed node to the root of the tree is the first child of its parent).

If we were to rewrite the above by replacing the boolean parameter with 2 functions, our algorithm is no longer expressed in terms of a single recursive function call for each on each of the children.

So we can see a distinction: algorithms in which we can do calculations for constituent parts of a composite data structure independently from the data structure of which they are a part, and those for which this is not possible.

Is there an accepted terminology for this distinction?

Edit to add:

In the context of parallel computing, recursive definitions of the first kind (no additional parameters in the recursive call) are automatically Embarrassingly Parallel


texts:
I have couple of questions about Turing machines:

What is the definition of the "reject" state in TM?
If the input was very small and, after one step, the machine gets to the end of the input, but it stands on regular state, it counts as "reject"? Or there is a special "reject" state, and if it won't get to this/those states, it doesn't count as a reject? (I know that in DFA, the reject states are just all the states that aren't "accept".)
I know that in aDFA, if we swap the reject and the accept states, we get the complement language. Does this work on TMs?
If I use only the TM's input cell (including changing their content), does it means I used $\mathrm{SPACE}(1)$ or $\mathrm{SPACE}(n)$?

Thanks a lot!


texts: Cuckoo hashing with a stash: how tight are the bounds on the failure probability?

texts:
I was reading this very good summary of Cuckoo hashing.

It includes a result (page 5) that:

  A stash of constant sizes reduces the probability of any failure to
  fall from $\Theta(1/n)$ to $\Theta(1/n^{s+1})$ for the case of $d= 2$
  choices

It references the paper KMW08. But KMW08 only has the result (Theorem 2.1) that:

  For every constant integer $s \geq 1$, for a sufficiently large constant $\alpha$, the size $S$ of the stash after all items have been inserted satisfies $Pr(S \geq s) =O(n^{-s})$.

Note that the $s$ in the different theorems is slightly different, in the first if the stash is of size $s$, it is not a failure, in the second, if the stash is of size $s$ it is a failure. This is why the first has $s+1$ and the second has $s$.

The difference between the two is then that the first uses theta-notation, whereas the second uses big-O notation. So my questions:

Do we know that the failure probability is $\Omega(n^{-(s+1)})$?
If so, do we know the constants in the $\Theta(n^{-(s+1)})$ expression?

And if so, which papers presented these results?


texts: What is the complexity of an in-place merge algorithm for forward iterators

texts:
I have written an in-place merge algorithm for forward iterators. My goal was to write an in-place merge algorithm to merge two sorted parts of a singly linked list without allocating extra memory to perform the merge. However, I have no clue how to determine its complexity.

Here is the corresponding pseudocode algorithm; I tried to represent the concept of iterators in pseudo-code, but that's not really pretty. Basically, an iterator is an object that points to a value in a sequence of elements. The only operations usable with a forward iterator are the following:

Check whether two iterators point to the same value (= and ≠); just remember that two values can be equal without being the same.
Copy the iterator (let it = other_it), basically create another iterator that points to the same value.
Advance the iterator so that it points to the next value in the sequence (advance).
Access the value it points to, generally to read or write that value (value_of), <- is used to assign the values.
Get the iterator pointing to the next value in the sequence (next_iterator).

The following function uses the set of operations defined above to implement an in-place merge algorithm.

function inplace_merge(first: ForwardIterator, middle: ForwardIterator, last: ForwardIterator)

    while first ≠ middle
        if value_of(middle) < value_of(first)

            # first should be in the right partition
            let tmp = value_of(first)

            # Put right in place
            value_of(first) <- value_of(middle)

            # Look for the place where to insert tmp
            let current = middle
            let next = next_iterator(current)

            # Move everything smaller than tmp to the left
            while next ≠ last and value_of(next) < tmp
                value_of(current) <- value_of(next)
                advance current
                advance next
            end while

            # Insert tmp in the right place
            value_of(current) <- tmp
        end if

        advance first
    end while

This algorithm takes two sorted ranges [first, middle) and [middle, last) and reorders them to produce a sorted range [first, last). The function compare is used to compare the elements. The algorithm more or less works like this: whenever an element in the left range is greater than the first element of the right range, we replace the first element of the right range in the left range, then we move every element to the left until we find the place where to insert the element that was originally in the left range (I know, plain-text descriptions sound a bit cryptic).

What is the complexity of this algorithm, considering that the complexity is determined by the number of comparisons performed between value with <?


texts: How is CFL-reachability solvable in exponential time and space?

texts: I have read a paper which mentions that CFL-reachability is solvable in exponential time and space. Intuitively, I suppose that one need to explore through all the sub-paths in the PDA for a CFL. However, I am not able to convince myself with this explanation. If someone could provide an explanation, it would be great.


texts: How come the Bernstein operator creates a polynomial of the same degree as its input function?

texts:
I read that the Bernstein operator

$$
\mathfrak{B}_f(t) = \sum_{i=0}^n f\left(\frac{i}{n}\right) \; B^n_i(t)
$$

applied to a polynomial $f(x)$ of degree $m \leq n$ with the Bernstein polynomial

$$
B^n_i(t) = \binom{n}{i} \; t^i \; (1-t)^{n-i}
$$

returns a new polynomial also of degree $m$. In other words, the Bernstein operator does not increase its degree when applied to $f$.

How is this possible? Since we're only sampling $f$ at a certain interval, wouldn't the original degree of $f$ become irrelevant? How can the degree of the result be smaller than $n$, since we will have at least one $t^n$ in the expression resulting from one of the Bernstein polynomials?


texts:
Okay so I have this recursive formula
$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2*O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$
$T\left(n\right) =T\left(1\right)\ +\ c_{2}*n\cdot\sum_{k=1}^{⌊\log\left(n\right)⌋}\frac{1}{2^{k}}=T\left(1\right)+c_{2}*(n-1)$
I've been trying for a few hours to prove the correctness of it by induction, I feel like I've tried everything. The closest I got was defining $n=2^{x}$ and prove the correctness for every $x$ but I can't seem to get the right answer.. How do you prove something like that?
The main question is how do I prove $T(n) = T(n/2) + c_{2}n = T(1) + c_{2}*(n-1)$


texts: Probability of winning a turn-based game with a random element

texts:
I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve.
Given a bag, which contains some given amount of white stones $w$ and some given amount of black stones $b$, two players take turns drawing stones uniformly at random from the bag. After each player's turn a stone, chosen uniformly at random, vanishes, and only then does the other player take their turn. If a white stone is drawn, the player, who has drawn it, instantly loses and the game ends. If the bag becomes empty, the player, who played second, wins.
What is the overall probability that the player, who played second, wins?
I assume it's a dynamic programming question, though I can't figure out the recursion formula. Any help would be greatly appreciated. :)
Example input: $w$ = 3, $b$ = 4, then the answer is, I believe, 0.4, which I arrived at after computing by hand all possible ways for the game to go, so not very efficient.


texts:
For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ :

Let's define as flow a sequence of element of the same type represented in the following diagrams using the same colour. Every flow must be routed into the same output stream keeping the elements ordered as found on the input stream:

Another correct solution that is more balanced than the previous one:

Considering also that:

After a number of elements (called $timeout$) on the input stream without any element of the type of a specific flow, that flow should be considered ended and the element found should be the starting point of a new flow

I have some questions:

Do you know any paper covering this kind of problems?
What is a good algorithm that maximise the throughput, in other words keeping the output stream balanced?

Update

Thanks to @D.W. for the comments, here some clarifications:

I am looking for an "online algorithm" where a "reasonable" latency is allowed therefore a lookahead-buffer/moving-window is definitely allowed
I am not looking for theoretical guarantees, I am looking for an approximate algorithm to try against few hundreds test cases made of [millions..billion] elements with a mix of few elephant flows and many mice ones.
The stream balance I am looking for should be considered over a period of time and not in an "absolute sense". In other words an algorithm that fills the first stream only then the second and then the third is as balanced as an algorithm that fill only the first stream


texts: What machine learning method for diabetes prediction SW?

texts:
I'm thinking of an application for diabetics, that, given previous values of blood glucose and insulin dosage, predicts the glucose level for the next few hours.

I know a few things about neural networks and perceptrons, but not much. And there are probably whole other worlds of other machine learning methods. So I'd like to ask about what way should I try to go.

My problem is below:

The app would probably have a (very) simplified model over what is the reality (what food, how much of it, did some sport lately?, what kind of insulin, etc.) - and there are also some "expert knowledge" rules that I know but that wouldn't get programmed into it (eg. if you have too low glucose level, your body compensates and makes it into a too high glucose level). I want to try how far can I get just with the glucose measurements (when and how much) and insulin dosage (when and how much).

I guess the main question it would be nice if the program solved is "Given my glucose history, what glucose will I have in a few hours if I take X units of insulin?" (That could indirectly solve question "How many units of insulin should I take if I want to have a good glucose level in a few hours?" but that's more complicated matter.)

The food is an important part of the question, but I think it's closely linked to the insulin - the two balance out: if you eat food, you take insulin. You don't take insulin without eating (it's more complicated than that, but I'm trying to make it simple), so I guess it could work without putting in the data about food.

Now the data (at least timewise) isn't uniformly distributed. Ideally it should be (regular measurements at the morning, noon, evening, etc.) but more often than not the measurements get skipped. So the training dataset would have to deal with having "holes" in it. I guess that's ruling out some methods.

What do you recommend to try? (Again, this is not anything medically professional and "to be used in real life" - it's just a proof of concept for me and a toy project to try to do some machine learning.)


texts: Type theory based automated theorem prover?

texts:
I know that there exist type theory based proof-checker, and I know that there are logic/sequent-calculus based automated theorem provers.

But I haven’t heard of a type-theory based automated theorem prover (nor of a sequent-calculus based proof-checker). Does a type-theory based ATP exist? (And a sequent-calculus based proof-checker?)

If not, why is it that type theory is more fit for proof-checking, and sequent-calculus more fit for proof-finding?


texts: Frankly speaking I have many problem with symbols in graph such as (s:s') or v\S or some symbols such as those that I mentioned . Can anyone suggest a good resource or a good tutorial on the net that has been discussed about these symbols and have clarified these symbols ?


texts: Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

texts:
I was binary indexed trees and I came across this article. One part of the justification was the following:

  Given that the (binary search tree) tree is perfectly balanced, a node N will have exactly
  $2^{i}-1$ children on each side, where $i$ is the position of the first
  1-bit in N, starting from 0, and counting from least significant to
  most significant. For example, for $N=11000$, we have $i=3$. For $N=111$, we
  have $i = 0$. This can easily be checked by recalling that the left
  children of $N$ consist of every number lower than $N$ (similarly for the
  right side). The “minus 1″ is there because we can’t count $N$ itself as
  being a child of $N$.

First off, I believe that the authors claim that

  "This can easily be checked by recalling that the left children of $N$
  consist of every number lower than $N$"

is not entirely accurate, as for example, in the following BBST:

      4
   /     \
  2       6
 / \     / \
1   3   5   7

The left children of node 6 do not contain every number lower than 6. Nevertheless, the formula $2^i - 1$ still holds true. Why does this work?


texts: What happens when all reference bits set to 1 in Second Chance Page Replacement Algorithm?

texts:
I have a sequence like 5577334... and there are 3 frames available.

After the 6th clock, all pages (5, 7 and 3) will have their reference bits set to 1.
Now, when 4 comes in, 5 will go even though its reference bit is 1 because of the FIFO rule but what happens 7 and 3' referance bits? Do they stay as 1? or Is 7's reference bit set to 0 since there is FIFO rule? or Are both 7 and 3' referance bits set to 0?


texts:
if I have an unsorted array with the length of $10^6$, which is filled with absolutely different float numbers, which sorting algorithm would be the best to use and why? And which one would be the worst? InsertionSort, QuickSort, MergeSort, HeapSort, BucketSort?
And would it be a difference if the float values would be integers and the array would not have the length of $10^6$, but $10^7$ or even $10^9$ or if it's not an array but a linked list?


texts: How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?

texts:
So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman algorithm. I've read the paper and have a doubt which I couldn't really figure out.

The algorithm works by removing the edge which has the highest value of "edge betweenness" in every iteration. Suppose I have a graph $G(V, E)$ such that $V = \{ v_{1}, v_2, \cdots , v_n\}$. Now suppose this graph is such that it has 2 distinct communities (something we already know but that's what the algorithm should detect). After the first iteration, it would remove the edge which has the highest value of edge betweenness. Now my question is, after this is done (or even after a few iterations), say I have any vertex $v_i$, how do we know which community this vertex belong to? Am I missing something here?


texts: Practical ml model explainability with graphs and prolog

texts:
How practical are logic engines for proof paths combined with knowledge graphs in Providing reasonable explainability for ML models trained using GNNs?
Adding more context. there is a history of logical reasoning (found in academic articles and in filed/granted patents) as a partial mechanism to building solutions to problems that are built on graphs. I am not an expert and thus I am not asserting that logic engines (like SWIProlog or any variant) are useful. I am curious about the use of ML models built on GNN (or GCN) methods where datasets are derived from larger and more complete knowledge graphs and any attempts to explaining how an observation is mapped to a prediction. This article (see sec. 4.1) cites work that uses proof paths to arrive at some approximation of explainability. I am looking for anecdotal examples of folks having worked with GNNs, KGs, and logic programming tools like prolog at showing how a prediction might be explained. If the cited work is sound, then this hints at logic engines being potentially useful for some use-cases.


texts: Reduction from knapsack problem to Integer relation that equals one

texts:
My question is related to the Integer Relation Detection Problem which can be formulated as:

$\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$

Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land x\in \mathbb{R}$, and $\exists i. a_i\neq 0$. $c$ and vector $\mathbf{x}$ are given, and the problem is to find a valid vector $\mathbf{a}$ that satisfies these constraints.

There are a few algorithms to solve this problem, listed on the wikipedia page linked.

My question: are there algorithms for a solution to the same problem with the modification that

$\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 1$?

Or equivalently (I believe),

$\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$?

The constant $b\in \mathbb R$ is a given.

On math.se I ask for a polynomial time algorithm or proof that none exist, with not much luck. Here I ask if a solution to this is equivalent to a solution the knapsack problem (can the knapsack problem be reduced to this), and this would thus be NP-hard.


texts: k-center problem: proof for Gon algorithm gives a 2-approximation

texts:
The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following function: $\max_{v\in V}\min_{c\in C}d(v,c)$.
I am trying to understand the proof that the $Gon$ algorithm is a 2-approximation. The algorithm arbitrarily selects the initial center and loops for $k-1$ iterations, where at each iteration it adds the vertex which is furthest away from its nearest center as a new center.
The full proof that this algorithm gives a 2-approximation is described in Gonzalez, Clustering to minimize the maximum intercluster distance. The cost of the optimal solution is $OPT(V)$ and they describe the term "$(k+1)$-clique of weight $h$ for $V$":

Set $T$ is said to form a $(k+1)$-clique of weight $h$ if the cardinality of set $T$ is $k + 1$ and every pair of distinct elements in $T$ are at least $h$ units apart.

The part that I don't understand is the following lemma:

Lemma 2.1: If there is a $(k+1)$-clique of weight $h$ for $S$, then $OPT(V)\geq h$.

My question is, what is the proof for this lemma?


texts:
As I understand the convoy effect, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not directly affected by the convoy.

How does this apply in the context of CPU scheduling? It does not seem to be an analogous situation.


texts:
I am trying to get better in proofs and deep understanding of concept of computational complexity. Unfortunately, so far, with no success.

In order to get more intuition, I decided to do more exercises, but most of them are still difficult for me.

I am looking for exercises with solutions in field of computational complexity. Sometimes on course pages there are homeworks with solutions.

I am asking if you aware about any decent course on computational complexity with exercises and solutions on course page, please let me know.


texts: What's the basic operation of a brute force median algorithm?

texts:
I have an algorithm that goes something like this

  $$\begin{align}
&\mathbf{ALGORITHM}\operatorname{BruteForceMedian}(A[0..n-1])\\
&\mbox{// Returns the median value in a given array $A$ of $n$ numbers. This is}\\
&\mbox{// the $k$th element, where $k=|n/2|$, if the array was sorted.}\\
&k\leftarrow|n/2|\\
&\mathbf{for}\ i\ \mathbf{in}\ 0\ \mathbf{to}\ n-1\ \mathbf{do}\\
&\quad\text{numsmaller}\leftarrow0\quad\hbox{// How many elements are smaller than $A[i]$}\\
&\quad\text{numeral}\leftarrow0\qquad\hbox{// How many elements are equal to $A[i]$}\\
&\quad\mathbf{for}\ j\ \mathbf{in}\ 0\ \mathbf{to}\ n-1\ \mathbf{do}\\
&\qquad\mathbf{if}\ A[j]<A[i]\ \mathbf{then}\\
&\qquad\quad\text{numsmaller}\leftarrow\text{numsmaller}+1\\
&\qquad\mathbf{else}\\
&\qquad\quad\mathbf{if}\ A[j]=A[i]\ \mathbf{then}\\
&\qquad\qquad\text{numequal}\leftarrow\text{numequal}+1\\
&\quad\mathbf{if}\ \text{numsmaller}<k\ \mathbf{and}\ k\le(\text{numsmaller}+\text{numequal})\ \mathbf {then}\\
&\qquad\mathbf{return}\ A[i]
\end{align}$$

I figure as this is a nested loop algorithm its efficiency class would be $O(n^2)$. I am just confused as to what the algorithm's "Basic Operation" should be. Is it the comparison operator down the bottom that (when correct) returns the median value of the array?


texts: "Searching and sorting" algorithm to find the natural logarithim of a number?

texts: Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm not allowed to use strategies that involve integration, bit manipulation, approximation formulas, or Taylor Series. Instead, we're asked to generate an array of values where at least one of them will be the answer, and then to find the correct value in that array. There must be some kind of established algorithm for this, but this and other resources haven't been helpful. I'm stuck. What should I be thinking about here?


texts:
$$T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + \sqrt n$$
Use the substitution method to prove $T(n) = O(n)$

What I have so far...
$T(n) \leq C_1n + C_2 \sqrt n-C_3 $
$T(n) \leq \frac{C_1n}{3} -C_3 + \frac{2C_1n}{3}+C_2 \frac{\sqrt {2n}}{3}-C_3 + \sqrt n$
I'm not really sure if I'm on the right track.


texts: (Nontrivial) Algorithms for finding the third largest element of a set

texts:
According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for finding the third largest in a set of $n$ distinct elements?

Given that the tight lower bound is still unknown, I want to know the algorithms currently published in papers (meaning that they are not trivial, for example, by finding and removing the largest and the second largest elements and finding the third largest one in $(n-1) + (n-2) + (n-3) = 3n - 6$ time) for finding the third largest element.

Searching for "algorithm finding the third largest element" in Google does not bring me useful references.


texts: Where is knowing the 2^k largest elements in a array useful?

texts:
I came across this question today on stackoverflow. It asks:

  Find the largest, $2$nd, $4$th, $8$th, ..., $2^{\log n}$-th largest element in an arrary. Use $O(n)$ algorithm. $2^k$

I've come across this before and know how it can be done, but I've been been trying to find examples of algorithms that incorporate the above into the actual algorithm for a while now since I'm curious about how it can be used in practice. However, I haven't had any luck at looking this up online haven't had any results. Therefore, I'm asking if anyone knows a formal name for an algorithm that solves the above or some examples of algorithms that use the above in some way or another.


texts: How to interprocess communication and scheduling algorithms interact?

texts:
I was listening back to a lecture I had, hinting on what we should revise for our upcoming exam. Since then I've covered all the parts, but having difficult in decrypting the following

  You might want to look at the interaction between scheduling algorithms and interprocess communication.

I understand both interprocess communication and scheduling algorithms but don't have an opinion/nor can find one on the link between the two. If anyone could inform me I'd really appreciate it.


texts: Hamming code distance and error detection

texts:
Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum
error rate under which error detection and retransmission mechanism (1 parity bit per
block) is better than using Hamming code? Assume that bit errors are independent of
one another and no bit error occurs during retransmission.

This is one of the questions from Tanenbaum book.

My approach is since there are 1000 data bits so, 2^r > = r+data bits +1

r = 10 and so the number of check bits is 10. So, the length of hamming code is 1010. Till here I am able to solve. But how will I get the error rate for the retransmission error detection technique compared to hamming code.

Can anyone explain how to proceed further ?


texts: Convert Subdivision Curve to Bezier Curve

texts: Wondering if there is a way technically to convert a Subdivision Curve into a Bezier Curve.


texts: How to get enclosed spaces from a series of connected nodes

texts:
I have a bunch of connected walls in a list and the data for them is like so:

Wall
{
   Node A;
   Node B;
}

Node
{
   float x;
   float y;
}

I want to find the rooms from the connected walls as an array of connected points to represent each room's perimeter.

This is an example visually of what i am trying to find:

The red dots are the nodes, and the lines are the walls, the numbers are the identified rooms that the walls created.

The walls can be at any angle, not sure if that matters though.

I am wondering what algorithms exist that can help me solve this problem, what is the best way to approach this?


texts: Can $f$ be not computable even if $L$ is decidable?

texts:
I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}$ is only computable iff the language

$$
L = \{s\#^j\sigma : s\in A^*, \sigma \in A, \text{ the }j\text{'th symbol of } f(s)\text{ is } \sigma\}$$

is decidable. Why is that? Couldn't a function $f$ be not computable even if $L$ is decidable?


texts: Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?

texts:
Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and hence NO for all others), but determining which input is the accepting one is undecidable?
Or is there a fundamental reason this cannot happen? Or is determining if this  problem exists undecidable?

I assume this is equivalent to asking: is there a property of TMs such that this property is true for exactly one TM and not true for all others such that determining which TM this is true for is undecidable?


texts: Finding a winning strategy for toads and frogs

texts:
Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm struggling with the strategy.

I read on it everything I could google out but turns out there's not that much to read about it as one may think - the most helpful thing I've found was probably an analysis by Erickson though it concentrates more on evaluating each position rather than some algorithm which would have to decide how to move a toad or a frog given a particular board as input. Same goes for "Winning Ways", where they evaluate a bunch of positions but don't give you too much insight on how to optimally play your game

The best playthrough strategy I could come up with is evaluating the value of the current  position (using "Winning Ways" and Erickson's tricks), evaluating the values of all the positions we can go to with  our toads/frogs in a given moment and then performing a move which leads to the lowest  value of the board so that our opponent has the worst moves to choose  from.

Is there anything better? Or if all the "good" strategies are very hard (as I said, I'm just starting out with my game theory interest), what's the best one that even someone with my experience could utilize? :)


texts: SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$?

texts:
I am trying to understand SVMs in depth watching lectures from MIT.
The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and margin boundaries as following:

Note that $\frac1{||\theta||}$ is the distance between the margin boundaries and the decision boundary ($\gamma_i$ is just the signed distance, but we don't care for this question).
We then proceeds to note that our goal is:

To maximize $\frac1{||\theta||}$
while minimizing the Hinge Loss

Now, it is apparent that these two terms will co-exist in the objective function we are trying to form $(1)$.
The Objective Function
$$\text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2 \quad (1) $$
Given the fact that he wants to create a minimization problem he describes the maximization of the distance to be equal to the minimization of it's inverse squared divided by 2, i.e:
$$\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$$
This does not make sense, as far as I can understand. In my mind this is the correct way of doing it:
$$\max\frac1{||\theta||}=\min||\theta||$$
Why did he insert a square and a division into the equation?


texts: Merge two sorted arrays without using additional memory

texts:
We have two sorted arrays of integers.
Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the second array.

For instance, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, the result should be $A=[1,2,3,4], B=[9,14,15]$. Entries are integers, and you can use only $O(1)$ extra memory for auxiliary variables.


texts: Knapsack approximation algorithm (weights scaling)

texts:
I am trying to prove the following Knapsack approximation algorithm, the problem definition:

Input:

A set $S$ of $n$ objects that contains weights and values:

$w_1,w_2,\ldots,w_n$ (weights)
$v_1,v_2,\ldots,v_n$ (values)

$W$ — The total weight bound.
Scaling factor $0 < c < 1$

Output:  Let set $\mathrm{OPT}(S)$ be the optimal solution (set of items with maximum values that their total weight is less than $W$) of the problem, I want to find a set $T$ whose value $\sum_{i \in T} v_i$ is a least $c \cdot \sum_{i \in \mathrm{OPT}(S)} v_i$.

The algorithm:

for $i$ from 1 to $n$:

$w'_i = c \cdot w_i$.

run the Dynamic Programing algorithm with the scaled items (table size $n \times cW$) — Knapsack Dynamic programming (Definition A).

I am not sure what is the exact reason why this is working.
I know that because I am only scaling the weights, the values are still the same, and the ratio between the weight/value of each item is remaining almost the same (depending on $c$).

I am also required to prove the correctness of this approximation algorithm by proving the following lemma:

  For every $i \in T$ there are items $i_1,\ldots,i_k \in \mathrm{OPT}(S)$ such that $v_i \geq c \sum_{j=1}^k v_{i_j}$.

The first direction of the proof is immediate if $i \in T \cap \mathrm{OPT}(S)$.

I got lost trying to prove the other side when $i \notin \mathrm{OPT}(S)$.

I would be thankful to get some explanation and guidance.


texts: What are the advantages of using FPGAs over GPGPUs? It seems like GPGPUs have the best of CPUs and GPUs combined.


texts: Do the two huffman trees have the same corpus?

texts:
Consider the following Huffman trees:

I was asked if those trees can have the same corpus. My answer was no, based on these calculations:

For the right tree:
$a_1 \le a_2$
$a_1 + a_2 \le a_5$
$a_3 \le a_4$
$a_1 + a_2 + a_5 \le a_3 + a_4$

For the left tree:
$a_1 \le a_2$
$a_3 \le a_4$
$a_1 + a_2 + a_3 + a_4 \le a_5$

Adding the last equations from each tree we have that:
$2a_1 + 2a_2 \le 0$ Which is a contradiction because frequency cannot be negative.

Nevertheless, I understood that there is a possibility that the two trees would have the same corpus. For instance, consider $1,1,1,2,3$.

So, where do my calculations go wrong?


texts:
" The 8080 was an 8-bit CPU, meaning it processed 8 bits of information at a time. However, it had 16 address lines coming out of it. The ‘‘bitness’’ of a CPU—how many bits wide its general-purpose registers are—is important, but to my view the far more important measure of a CPU’s effectiveness is how many address lines it can muster in one operation. In 1974, 16 address lines was aggressive, because memory was extremely expensive, and most machines had 4K or 8K bytes (remember, that means 4,000 or 8,000) at most—and some had a lot less.
Sixteen address lines will address 64K bytes. If you count in binary (which computers always do) and limit yourself to 16 binary columns, you can count from 0 to 65,535. (The colloquial ‘‘64K’’ is shorthand for the number 66,536.) This means that every one of 65,536 separate memory locations can have its own unique address, from 0 up to 65,535."

my questions are how 16 bits address lines can address 64KB?,since 16 bits can only address 64kbps.

and what is segment?

thanks in advance


texts: Upper bound for runtime complexity of LOOP programs

texts:
Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions.
Furthermore primitve recursive functions can (as far as I understood) compute anything that isn't growing faster than $Ack(n)$.

Is this implying that the upper bound runtime complexity for LOOP programs is $O(Ack(n))$? And are there functions similar to Ackermann's function, which can't be computed by primitive recursive functions, but grow slower than $Ack(n)$?

(sorry for spelling and grammar)


texts: Are there any methods to quantify complexity of finite problems?

texts:
On page 348 of "Sipser M. Introduction to the Theory of Computation. Cengage Learning; 2012 Jun 27", it says

  Perhaps at some time in the future, methods that can quantify the complexity of finite problems will be developed. But current methods are asymptotic and hence apply only to the rate of growth of the complexity as the problem size increases --- not to any fixed size.

My question is, "are such methods developed currently?"


texts: improving java 8's implement to hash map using avl tree

texts:
Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup.

Will changing this implement to an avl tree change this O(n) case to something better (without changing the other complexities)?

here are some notes on it:

  This map usually acts as a binned (bucketed) hash table, but
    when bins get too large, they are transformed into bins of
    TreeNodes, each structured similarly to those in
    java.util.TreeMap. Most methods try to use normal bins, but
    relay to TreeNode methods when applicable (simply by checking
    instanceof a node).  Bins of TreeNodes may be traversed and
    used like any others, but additionally support faster lookup
    when overpopulated. However, since the vast majority of bins in
    normal use are not overpopulated, checking for existence of
    tree bins may be delayed in the course of table methods.

  Tree bins (i.e., bins whose elements are all TreeNodes) are
    ordered primarily by hashCode, but in the case of ties, if two
    elements are of the same "class C implements Comparable",
    type then their compareTo method is used for ordering. (We
    conservatively check generic types via reflection to validate
    this -- see method comparableClassFor).  The added complexity
    of tree bins is worthwhile in providing worst-case O(log n)
    operations when keys either have distinct hashes or are
    orderable, Thus, performance degrades gracefully under
    accidental or malicious usages in which hashCode() methods
    return values that are poorly distributed, as well as those in
    which many keys share a hashCode, so long as they are also
    Comparable. (If neither of these apply, we may waste about a
    factor of two in time and space compared to taking no
    precautions. But the only known cases stem from poor user
    programming practices that are already so slow that this makes
    little difference.)


texts: What is the best hash functions for millions of String keys?

texts:
I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value.

The problem that the retrieval process is too slow and I want to improve the retrieval. I wonder if there is a good hash function to help me with this task.

I am using Separate Channing for resolving the collision

the current hash function

hash = 0
for i = 0 : strlen
    hash = hash * 31 + getChar(strlen, i)

So My question: Is there a better hash function to minimize the collision between the keys?


texts: Definitions of an algorithm running in polynomial time and in strongly polynomial time

texts:
Wikipedia defines it to be

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ for some constant k.
The algorithm runs in strongly polynomial time if [8]

the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input
instance; and

the space used by the algorithm is bounded by a polynomial in the size of the input.

In Bernhard Korte, Jens Vygen, Combinatorial Optimization:

Definition 1.4.
An algorithm with rational input is said to run in polynomial time if

there is an integer k such that it runs in $O(n^k)$ time, where n is the input size, and
all numbers in intermediate computations can be stored with $O(n^k)$ bits.

An algorithm with arbitrary input is said to run in strongly
polynomial time if

there is an integer k such that it runs in $O(n^k)$ time for any input consisting of n numbers and
it runs in polynomial time for rational input.

Please correct me if I am wrong. Following are the literal differences I noticed:

For polynomial time algorithms, Korte and Vygen's definition is "the Wikipedia's definition + polynomial storage space".

For strongly polynomial time algorithms, Korte and Vygen's definition and Wikipedia's definition both require polynomial time in the input storage size. But K and V's additionally requires polynomial time in the number of numbers in any input, while Wikipedia's additionally requires polynomial storage space in the input size.

So are K and V's and Wikipedia's definitions for these two concepts equivalent, respectively? What other differences and relations are between them?
Thanks and regards!


texts: Wanted: Concrete Example of Busy Beaver Holdout

texts:
I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' machines whose halting behavior is as of yet unknown.

Can someone provide me with a concrete example of such a 5-state 2-symbol current (or as close to 'current' as possible) 'holdout'? When looking around on the net, I am finding lots of 'champions', but never any 'holdouts'. Does someone have one or more examples, please?

Thanks!

EDIT

THe linked question asked about 'short programs', but this question is specific to Turing-machines and the Busy Beaver problem. And yes, while that question solicited a response with two Busy Beaver Holdouts of the right kind (Thanks Ricki!), the source provided is 27 years old ... I would like to be able to point to any of these machines and say that these are 'current' holdouts, so if anyone can tell me whether these are still holdouts, or knows of any other, more current, holdouts, I would appreciate it. So, I am holding out for someone who maybe has some more current knowledge regarding the status of these busy beaver holdouts. Thanks!


texts: Median of two sorted arrays of different size in logarithmic time?

texts:
The solution given in Cormen is as follows:

Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary search on A only, then how will we get the median if it lies in B. Also the pseudo code is less than understandable. Can anybody simplify it to me.


texts: Algorithm for enumerating over all possible pairs, by size (with some added conditions)?

texts:
Is there a way to enumerate, by size (the size of a pair is ||+|| but if the enumerator represents them in some different way than simply concatenating them (like via some different encoding) then we are just talking about the size || of the string  in the enumeration that encodes the pair (,)), from biggest to smallest, all pairs $(x,y)$ from two enumerable, countably-infinte sets, $X$ and $Y$, of words, in such a way that there is one element (in the enumeration) of each size (even above some min size: $|x|min + |y|min$ ($|x|min$ being the shortest string in $X$ and $|y|min$  being the shortest string in $Y$) would be fine), with the added condition: the enumerator needs to represent/ encode the pairs it enumerates in such a way that it doesn't "mangle" the pairs. To define mangle: we need to be able to extract (read) both the $x$ and $y$ encoded/represented in any string $s$ in the enumeration in poly time*.
*by poly time I mean measured in length of string in the enumeration (so if $|s|$ = $l$, for some $s$ in the enumeration, I would need to be able to recover $x$ and $y$ in fewer than $l^k$ steps.
Just to reiterate, whatever encoding the enumerator uses to generate its representations of the pairs $(x,y)$...one needs to be able to decode any string $s$ in the enumeration back into the $(x,y)$ in $|s|^k$ time. PLUS there has to be at least one string of each length (again, above some min length would be fine) representing some valid pair. So, given a natural number $b$ (maybe above some smallest number $m$), there is an element of the enumeration $s$ such that $|s|=b$ and we can decode that string of length $b$ back into ($x,y$) in less than $b^k$ time (and just as an aside, I think this also means $|x,y|<b^k$).


texts:
I find the need to use an explicit level numbering for a tree.
i.e. in the tree:

    A
   / \
  B   B
 /\   /\
C  C C  C

should I number the level C the 3rd and A as the first, or the opposite?
As going 'up' the tree is going towards A; should the numbering reflect that as well?
 If can, please supply an authorized CS reference.

Thanks!


texts:
There was a comment here that " It is possible in principle to reduce the factorization of a $256$-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension $N\times N$ where $N\leq c\cdot256^c + c$ for some hopefully small constant $c$. However the computation of a nice upper bound on $c$ would probably take substantial effort. It's possible c is no more than 2 or 3."

Is it possible to convert factoring integers to calculating permanent? That is given $\log N$ bit integer to factor, how can one reduce factoring such an integer to calculating permanent of $(\log n)^c\times(\log n)^c$ matrix for a fixed $c$?

I also ask if computing $a(a+1)(a+2)\dots(a+n)$ with $a\in\Bbb N$ is also easy (done in $\log^cn$ steps if permanent of $N\times N$ matrix is easy (done in $N^c$ steps). Note that at $a=1$ we have $n!$, and permanent of all $1$ matrix needs $n\times n$ size and hence needs $n^c$ time even if permanent is easy.


texts: Tight bound on the number of divisors of n

texts:
The inner loop of this pseudocode runs only for the divisors of n

for i=1 to n:
   if(n%i==0):
      for j=1 to n:
         Do something in constant time

If I can get a bound on the number of divisor of n(The condition in the if statement) then I can get its time complexity.Please Help ?


texts: Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$?

texts:
I'm working with this definition for one-way functions:

  We call $f$ a (strong) one-way function if

  it is computable in polynomial time
  for any polynomial time randomized algorithm $B$ and any constant $c$
  $$
\mathbb{P}\big(f(B(f(x))) = f(x)\big) = o(n^{-c})
$$
  where $x\in\{0,1\}^n.$

And this defintion for hard-core bits:

  Let $f : \{0,1\}^n \rightarrow \{0,1\}^k$ and $b : \{0,1\}^n \rightarrow \{0,1\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$,
  $$
\mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\,.
$$

And I'm asking myself whether, if $f$ is one-way and finding $x$ from $f(x)$ is polynomial time reducible to finding $b(x)$ from $f(x)$, $b$ must be hard-core. One way to structure this argument is like so:
$$
\text{finding $x$ reduces to finding $b(x)$} \implies \big(f\text{ is one-way} \implies b\text{ is hard-core}\big)
$$
Or by contrapositive:
$$
\text{finding $x$ reduces to finding $b(x)$} \implies \big(b\text{ isn't hard-core} \implies f\text{ isn't one-way}\big)
$$

So suppose finding $x$ reduces to finding $b(x)$ and $b$ isn't hard-core. Then the obvious strategy is to go through the reduction but instead of computing $b(x)$ deterministically, we make a good guess using some algorithm $B$ which must exist because $b$ isn't hard-core. Since we have a non-negligible chance of success to guess $b(x)$ correctly, we end up with a non-negligible chance to guess $x$ correctly and so $f$ isn't one-way.
But there's a point here where trouble comes in. That is, the reduction might involve computing $b(x)$ multiple times for various values of $x$. While we know the probability of computing a single $b(x)$ for a random $x$ correctly, I don't have any handle on the probability of success for a sequence of calls $b(x_i)$ where the $x_i$ are arbitrarily correlated.


texts: maximum matching number decreases when vertices collapse?

texts:
It seems that the maximum matching number decreases when some independent (not connected) vertices collapse into one vertex, but I don't know if it is absolutely true.
Would maximum matching number increases when two vertices are connected to form a new edge?

Any proof? Thanks!

Definitions:
Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

A maximum matching (also known as maximum-cardinality matching1) is a matching that contains the largest possible number of edges.


texts: prove that the language LRE is decidable

texts:
given the language LRE= { 〈M〉 | L(M) ∈ RE }
prove that the language can be found in R( which means it's decidable).
if i use reduction, how can i use for example ADFA language to solve it?
and is there any other way to prove it except for reduction?
i'm studying to an exam so it would help me a lot.


texts: Prove that regular languages are closed under the cycle operator

texts:
I've got in a few days an exam and have problems to solve this task.

Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation
$\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$
And now we should show that $\operatorname{cycle}(L)$ is also regular.

The reference is that we could construct out of a DFA $D=(Q,\Sigma,\delta, q_0, F)$ with $L(D) = L$ a $\epsilon$-NFA $N$ with $L(N) = \operatorname{cycle}(L)$ and  $2 · |Q|^2 + 1$ states.


texts: how two phase commit ensure serializability

texts:
Two phase commit is used in distributed transaction. For example, a client sends a transaction to two databases with a coordinator.

step1: client get a global transaction id from coordinator
step2: client send the transaction to two databases respectively
step3: client send the commit flag to coordinator
step4: coordinator send prepare flag to two databases, and two databases response prepare ack
step5: coordinator send commit flag to two databases, and two databases response commit ack
step6: coordinator response commit ack to client

My questions are

What is the global transaction id in step1 used for?
And two phase commit is used to ensure the atomic in ACID, but how does it ensure the serializability? For examples, if client A sends transaction A and client B sends transaction B to databases simutaniously, then two databases may execute two transactions in different orders. Then two databases may end with non consistent states.


texts:
On an old worksheet I came across the question

If L1 and L2 are two Turing decidable languages, then show that 1∪2 and 12 are Turing decidable languages (high-level description with stages is enough).

How do I go about answering this without being given a language to work from?


texts: Minimizing the maximum Manhattan distance

texts:
Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself.

The points are inside a grid, –10000 ≤ Xi ≤ 10000 ; –10000 ≤ Yi ≤ 10000,  N<=100000.

In the example below the points are (1, 1), (6,1), (6,6), (3,4) and the smallest maximal Manhattan distance (equal to 5) is achieved from points (4,3), (5,2) (marked with E).

Is there an efficient algorithm to solve the problem?
The restrictions are quite large so the brute force approach wouldn't work.

Edit: problem: http://varena.ro/problema/examen (RO language)


texts: Is there any implementation of AO* algorithm?

texts:
I'm trying to solve And-Or Graph, and I find AO* algorithm can handle it. Someone said it's already used in AI, but I can't find it in detail.

Have it implemented? Or it's just a pseudocode that can't realized? If it exists, where can I find it? Or any suggestions to help me to implement it? I'm really appreciate your help.


texts: Program Counter Incrementation When instruction Is More Than One Word

texts: How is program counter(PC) incremented when instruction takes more than one word? How does PC know when to increment by one word or by more than one word since incrementation is done before decoding the instruction(if I am correct)?


texts: Removing constant symbols from language to prove irregularity

texts:
I'm confused about a solution I saw about the following language not being regular:\begin{equation*}
  L=\{0^n ~1 ~2^n : n >0\}
\end{equation*} The example solution said that $L$ was "the same as":\begin{equation*}
 L'=\{0^n1^n : n > 0 \}
\end{equation*} so it wasn't regular. I understand why $L'$ isn't regular, but I don't understand how $L$ is the same as $L'$. How can you eliminate that middle symbol?


texts: Strategy to create a testbed and gold standard

texts:
I need to create a correct evaluation of the method I'm proposing. The problem is that in the field I'm working on there is no benchmark that I can use for this purpose. On the other hand, my method has to run, as much as possible, on top of "real documents", but these documents are mostly private and created by industry.

The documents are based on the AutomationML language, which is XML-based, and I do have some "real" ones. Until now, I have created the documents manually, and have also automatically generated them based on a given seed document and the AutomationML XML-Schema to ensure that the generated documents are syntactically correct. Also, they are generated following a uniform distribution.

I would like to extend the automatic generation but for this, I don't know how to automatically create the gold standard. I would appreciate any hints regarding this.


texts:
A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then,
My question is: Can a schedule be conflict serializable but not serializable?
Please explain why.


texts: Largest subset such that for every two elements one of them divides the other

texts:
So the problem states:

  An array of $N (1 \leq N \leq 2000)$ natural numbers is given. Find
  the cardinality of the largest subset of that array such that for
  every two numbers $A$ and $B$ either $A|B$ or $B|A$ (or both).

I know you don't like it when people post questions without trying anything, but the only thing I can possibly think of (that would work) is brute force, which would mean exploring every possible subset and then checking the given condition, again, by brute force.

But since the time complexity of subset exploration is $O(2^N)$, and $N = 2000$ in the worst case, this solution becomes pretty useless.

Other thing I had in mind was some kind of divide and conquer algorithm, similar to merge-sort. But I can't think of a way I'd use the results of two (left and right) subarrays to compute the result for their union.

So, any ideas?

Thanks.

EDIT:
The brute force solution I've made that seems to be working (C++):

int largestSubset(const vector<int>&arr, int i, vector<int>&subset, int j){
    if(i == arr.size()){
        //brute force check
        for(int k = 0; k < j; k++){
            for(int s = k + 1; s < j; s++){
                if ((subset[k] % subset[s] != 0) && (subset[s] % subset[k] != 0)){
                    return 0;
                }
            }
        }
        return j;
    }

    //skip the i-th element
    int count1 = largestSubset(arr, i+1, subset, j);
    //include the i-th element
    subset[j] = arr[i];
    int count2 = largestSubset(arr, i+1, subset, j+1);

    return  max(count1, count2);

}


texts: Maximum Enclosing Circle of a Given Radius

texts:
I try to find an approach to the following problem:

  Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the set. The running time should be $O(n^2)$.

At first it seemed to be something similar to smallest enclosing  circle problem, that easily can be solved in $O(n^2)$. The idea was to set an arbitrary center and encircle all point of $S$. Next, step by step, replace the circle to touch the left/rightmost points and shrink the circle to the given radius, obviously, this is not going to work.


texts: Result of ANDing & ORing functions expressed as CDNF & CCNF

texts:
I came across following fact:

  If we AND two functions expressed as CDNF (Canonical Disjunctive Normal Form), then the result contains sum of commont minterms.

For example consider two functions $f_1$ and $f_2$ on three variables $A,B$  and $C$ expressed in CDNF. Then they will have eight minterms: $m_0$ to $m_7$.

If

$f_1 = \sum ({m_1,m_2,m_3}) = m_1+m_2+m_3$  and

$f_1 = \sum ({m_2,m_3,m_4})=m_2+m_3+m_4$

then,

$f_1.f_2=m_2+m_3$ as $m_2$ and $m_3$ are common in both $f_1$ and $f_2$.

However now I am thinking about what will be the result of

$f_1+f_2$

If we consider $F_1$ and $F_2$ on three variables $A,B$  and $C$ expressed in CCNF (Canonical Conjuctive Normal Form) as follows:

$F_1 = \prod ({M_1,M_2,M_3}) = M_1.M_2.M_3$  and

$F_1 = \prod ({M_2,M_3,M_4}) = M_2.M_3.M_4$

then what will be the result of
$F_1.F_2$
$F_1+F_2$

After some thinking, I came up with following:

$f_1+f_2$ will be

  union of minterms in both functions, that is sum of all minterms with the common minterm appearing only once.

Thus, $f_1+f_2 = m_1+m_2+m_3+m_4$
$F_1.F_2$ will also be

  union of the maxterms in both functions. That is the product of all maxterms with the common maxterms appearing only once.

Thus, $F_1.F_2=M_1.M_2.M_3.M_4$
I found it very tricky to think about $F_1+F_2$. In the end I felt it should be

  AND of OR of two different maxterms with no OR of same and common maxterms.

$\therefore F_1+F_2= (M_1+M_2)(M_1+M_3)(M_1+M_4)(M_2+M_3)(M_2+M_4)(M_3+M_4)$
So $(M_2+M_2)$ and $(M_3+M_3)$ will not be there.

as $f_1.f_2$ was

  OR of AND of two same and common minterms with no AND of different minterms.

So above $f_1.f_2$ was actually $m_2.m_2+m_3.m_3$. This because AND of different terms will be $0 (false)$ and $0+a=a$

However, if I am correct with $(M_2+M_2)$ and $(M_3+M_3)$ being not part of $F_1+F_2$, I don't understand why that would be. If I think as dual of "AND of different terms will be $0 (false)$ and $0+a=a$", it would be "OR of same terms will be $1 (true)$ and $1.a=a$". But I dont get how OR of same terms will be 1?

I am just trying to find some pattern here and didnt found this explained anywhere.

Q. Am I correct with these three guessings?

Q. If yes then I will like to know about above bold-faced question: how OR of same terms will be 1?


texts:
A question on SO about complexity of sorting vectors of vectors got me thinking about the complexity of comparing 2 vectors.

Let's consider vectors of average size 1) N.

The first formula we get for the comparison of 2 vectors is O(N), but my intuition says it could be lower. Worst case scenario is N comparisons (vectors are equal), but best case scenario is 1 comparison (vectors differ by first element). Obviously the range of values held is very important here. A vector of 64 bits integers (domain of 2^64 values) is much much more likely it will end the comparison early on than say a vector of 1s and 0s (domain of 2 values).

Let M be the size of the domain (number of values each element can hold; the size of the alphabet)

Now when we consider that M is fixed (which it is) we might be tempted to say that the complexity is still O(N), no matter how large M is. It may have a very small factor O(f*N), but it is still O(N). Mathematically we consider the greatest power in the polynomial. Intuitively a large enough N will hide the factor (which is the probability of 2 elements being equal, or a product of probabilities, correct me if I am wrong).

But... in real life (computation real life) a vector doesn't have unbounded size. A 64 bits integers vector of size 2^64 (N = M = 2^64) would need about 10^8 terra and even a 32 bits integers vector of size 2^32 (N = M = 2^32) would require 16 giga. So I would say it is safe to assume 2) that N < M: the size of the vector is less, much more less than the size of the alphabet.

(for me, intuitively that means that the time complexity doesn't get the chance to "explode" because of the very small factor and because N doesn't get the chance to get sufficiently big - compared to M)

So considering N < M does this mean that for a large fixed alphabet (e.g. 2^32 or 2^64) we can recompute the complexity of vector comparison to something lower than O(N)?

Or am I way off?

1) size of vector = number of elements (not size in bytes)

2) for vectors of large ints and for most real life uses (completely ignoring the rare applications that deal with very very large vectors)

extra) I think it goes without saying that element comparison is O(1)


texts: How would a priority queue be implemented in a functional programming language?

texts:
How would a priority queue be coded efficiently in a functional programming language? I'm new to functional programming, but I'm having difficulty understanding how a data structure that seems to require mutability would be coded in a functional programming language, or how to take advantage of lazy evaluation to pull this off.

Are there any working examples of priority queues being coded in a functional programming language?


texts: Variant of the "Stable Roommates Problem" when room has not 2 but "n" mates

texts:
I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm?

To summarize, the problem is the following: Given a set of $n$ people, and a symetric $n\times n$ affinity matrix between each person, find an optimal disjoint set partition of the people into $m$ groups of a given size, maximizing the global "affinity score" (the sum of each pair affinity in each group).

Why this question? I'm organizing a wedding ceremony with around 60 people, grouping people into tables of 6 to 8. Each person pair has an affinity weight, ranging from $-\infty$ (they can't stand each other) to $+\infty$ (they better be together).

This question is somehow related, but unfortunatly does not have any answer.


texts:
The more I think about it, the stranger the concept of having a number type, which is a super-type of integers, rationals and reals seems to be. One thing that comes to mind is the Wittgenstein's concept of class families (where objects are grouped into families, even though neither one is a sub-type of the other, but have some "common property", not necessarily common to all objects in the family). Certainly, not a hierarchy.

And yet, in languages like Java, Common Lisp, Haskell and possibly lots of others there is a concept of a numerical super-type for types like integers, reals, complex etc.

Is there any computer-science-related explanation of existence of such super-type, or is this simply a convenience, which has no deeper meaning?


texts: Given a digraph and a root, find a tree that minimizes the sum of edges

texts:
Instance: a directed graph  $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$.
Solution: A directed tree with root $v$.
Objective: Minimize total weight.

My formulation:

My AMPL code:

param n >= 1, integer;  # number of vertices

set V := 0..n-1;
set E within {V,V};
param r := 0;

param w{E};  # edge weights

#Variável que determina se a aresta pertence a árvore
var x{V,V} binary;

#Variável que determina se existe um caminho de v pra r
var y{V} binary;

minimize maed :
  sum{(u,v) in E} x[u,v] * w[u,v];

subject to UreachR {(u,v) in E} : y[u] >= x[u,v];
subject to VreachR {(u,v) in E} : y[v] >= x[u,v];
subject to rest3 {u in V : u != r} : y[u] = sum{v in V} x[v,u];

The formulation and corresponding code above is returning A subgraph of G with cycles... I want a restriction that can eliminate them (make a tree).


texts:
How to prove that $\mathsf{NP}^A \neq \mathsf{coNP}^A$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds.

I know the proof where you show that there is an oracle $A$ such that $\mathsf{P}^A \neq \mathsf{NP}^A$ and an oracle $A$ such that $\mathsf{P}^A = \mathsf{NP}^A$. I have a hint that I should find such oracle $A$ by extending the proof of $\mathsf{P}^A \neq \mathsf{NP}^A$ but wherever I search and read, it is "obvious" or "straightforward" everywhere but I just do not see how prove it at all.


texts: Solve Time Complexity problem using Time Hierarchy

texts:
I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use Time Hierarchy.

I need to show that the following are either equal, on inclusive of one another...

TIME($2^{n^2}$) and TIME($n^3 \times 2^n$)

My intuition tells me that...

TIME($n^3 \times 2^n$) $\subset$ TIME($2^{n^2}$)

Can someone explain how I can prove this using the rules of Time Hierarchy?


texts:
There are a couple of definitions of recursively enumerable, for example in Judah: $A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0_1$ formula $\varphi(x)$ such that

$$A:=\{n \in \mathbb{N}: \mathbb{N} \vDash \varphi(n)\}$$

In Shoenfield: A predicate $P$ is r.e. if there is a recursive predicate $Q$ such that

$$P(\bar{a}) \leftrightarrow \exists x Q(\bar{a}, x)$$ for all $\bar{a} \in P$. And in here there is another one A new definition of recursively enumerable set?.

My question is: Are the definitions of recursively enumerate equivalent? Why?


texts:
We know that general palindromes cannot be decided by a DFA.

Howeve if you restrict to case of even length palindromes, does a DFA need exactly $2^{2k}$ states where $2k$ is length of palindrome the language needs to accept?

I get this as lower bound from Myhill Nerode aplication.

From answers below, my lower bound is wrong. What is the correct bound from Myhill Nerode?

How do you show the upper bound?


texts: Online set cover variant? Routing of requests

texts:
We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially.

Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are two paths from $s1$ to $s4$ i.e., path1 : $s1-s2-s3-s4$ and path 2: $s1-s5-s6-s4$.

Further, each node on the path has an associated table that records entries. When a path is chosen, an entry may or may not be added to each node on the path. Whether an entry is added or not depends on the nature of the request, but that is not relevant here. Also, the node tables are independent of each other.

Each table has a limit on the number of entries. Suppose each table can hold a maximum of $n$ entries. When a table is full, that node cannot be chosen on any path. The blue boxes in the figure represent the percent full of each table. The node $s3$ is more utilised than the other nodes. If $s3$ becomes full, the path $s1-s2-s3-s4$ cannot be used to route any more requests.

Now, the challenge is to route the maximum number of requests, as they arrive sequentially. Here is what I have so far.

Heuristic 1: Choose the path with the least total new table entries added. Using this heuristic, however, can lead to non-uniform utilisation of the tables. Suppose that on the $s1-s2-s3-s4$ path, entries are added only at $s3$. And using the other path, entries are added at $s1$, $s5$, and $s6$. Heuristic 1 will choose path 1, but this may lead to faster fill-up of $s3$ and path1 cannot be used to route more requests.
Heuristic 2: Choose a cost function for each node based on a) cost to add new entry and b) percentage utilisation of table. Then choose the path with least total cost.

Let us define the cost metric as $ cost_{node} = cost_{new\;entry} + \frac{|existing\;entries|}{n}$

Using this heuristic, path 2 will be chosen, given the conditions stated above.

Now my question is two fold:

Is there a better way of going about this?
Given the two heuristics, how would I go about showing the competitive ratio?

Any help in this regard is appreciated.

Edited:
For the sake of simplicity, let us consider for each node on a candidate path, a new table entry is added with a probability $p_i$ and not added with probability $1-p_i$.

Note:

When a request arrives, and we get a set of candidate paths, we can know in $\mathcal{O}(1)$ time for each node in the path, whether it will have an entry added to its table or not. So in $\mathcal{O}(l)$ time we can know the number of  new table entries for a path, where $l$ is the length of the path.
We have global knowledge about the number of entries in a table of each node at every time instant.


texts: Which algorithm suits best for AST pattern matching

texts:
I want to create a refactoring/analysis for java tool in Haskell.
I can write the monadic parser, but I don't have clarity about next steps.
I could express AST transformations via functions and built-in pattern matching, but is that the right approach?
I've searched a bit on tree graph pattern matching and found a few papers that I'm not sure are related to my specific problem, so I would appreciate a guidance to appropriate solution for this.
Maybe I should read some book on static analysis first or something?


texts: Predicate Logics - double negation HELP me understand

texts:
Sorry for maybe a silly question but i need to understand how
¬(¬∀x ¬A(x)) equals ∀x ¬A(x)

In my mind, the negation before the parenthesis will be applied to both ¬∀x and ¬A(x). So it would look like this:

¬(¬∀x ¬A(x)) = ¬¬∀x ¬¬A(x)

A double negation would become positive and would then let
¬(¬∀x ¬A(x)) equal to ∀x A(x).

So, why would ¬(¬∀x ¬A(x)) equal ∀x ¬A(x)?
Why wouldnt ¬(¬∀x ¬A(x)) equal ∀x A(x)?


texts: How do I solve a search problem on an infinite graph?

texts:
I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \times V$ is an undirected set of edges connecting vertices. Both $V$ and $E$ can be infinite. Each edge has an associated cost $c: E \rightarrow \mathbb{R}$ and the cost of a path (an ordered set of edges) between adjacent vertices that leads from the start to the goal is the sum of the cost of all of its edges. My goal is to find the path with minimal cost (assume it exists).
From my understanding, because this graph could possibly have an infinite branching factor, A* is not guaranteed to return a solution (or terminate). Are there any viable alternative algorithms that are designed for handling graphs with large or infinite state and action spaces? I'm not looking for guaranteed termination or optimality, just some names of algorithms that might be used in these sorts of problems as my search for "heuristic search infinite state space" doesn't turn much up.


texts: Virtual Address and Physical Address Space

texts:
A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8K. How many entries are needed for a conventional page table ?

The answer is 2^35 entries

Why not (2^32) / (2^13) = 2^19 entries...?

My doubt here is why does the number of page table entries depend on virtual address space rather than physical address space?

What does it mean to have more virtual address space than physical address space? The process can only access as many pages present in the physical memory. So it makes sense to have same have both virtual and physical memory address space same. But why have more virtual address space?
Does it mean 2 different virtual address entries are mapped to the same physical location in the same page table? Guess that would lead to inconsistency right? Can someone help me get the bigger picture here..... I really need to internalize this concept.


texts: Neural Network Inputs For Video Game use (DotA 2)

texts:
I am currently working on a project to build and train a neural network to play DotA 2 (at least be able to play like a really bad human).
The thing is all the neural network I have built before were made to play small games like 2048 or snake so the inputs were pretty straight-forward. (e.g for 2048 each input neuron was a tile of the game and the value was normalized from 2-2048 to 0-1).

But for DotA2 things get really more complicated because I have to encode a huge amount of possible objects: heros, creeps, towers, etc...
At the moment I am thinking about maybe dividing a simplified version of the map into tiles (about 3000 tiles) and have each tile related to 1 input but then again, how to encode such complex data ?

Hoping to read from some of you experts out here,
Thank you


texts: Geometric interpretations of midpoint algorithm, homogeneous linear least squares and nonlinear least squares method in 3D reconstruction?

texts:
In "Multiple View Geometry in Computer Vision" Chapter 12. Structure Computation, page 310-313, triangulation is used for point 3D reconstruction. There are three methods mentioned:

Midpoint method that "finds the midpoint of the common perpendicular to the two rays in space".
Linear triangulation methods that uses SVD to solve homogeneous equation Ax = 0. In this method algebraic error is minimized.
Nonlinear triangulation method that uses iterative optimization algorithms e.g. LM to solve a nonlinear least square equation Ax = b. The "gold standard" reprojection error is minimized.

My question is:

What are the geometric interpretations of the three methods?
What are the differences between the three triangulation methods above?

I did some research and found some useful information:

This post explains that algebraic error assumes noise comes from 3D points, while reprojection error assumes noise comes from 2D image

These slides introduce three methods but did not provide explicit geometric interpretations.


texts: Designing a rationing algorithm for a store

texts:
Suppose I have a store and I have n units of item x. I want to sell all n units at the end of the day. I do not know how many customers will be coming in today. One customer could theoretically come in and buy all remaining units. This would not be desirable, as the next customer would not be able to buy this item, and would end up frustrated that we do not keep enough in stock.

In general, how does one design a rationing algorithm that balances the need to sell as much quantity as possible with serving the most amount of (unknown number of) customers? Is this even possible?


texts:
I have the following problem:

  Given positive integers $a, b, c, d, n$, compute the maximum possible value (which is garuanteed to be less than $10^9$) of the function $$f(x,y) = cx + dy$$ where the only pairs $(x, y)$ that are considered for which $x$ and $y$ are positive integers and $ax + by \leq n$.

I'll be very grateful for any tips about which method could be used to solve this.


texts: Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?

texts:
I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set.

I was told that the potential function:

$$ \Phi(x_1, ... , x_n ) = \sum_i log(w[x_i])$$

would work (where $w[x_i]$ is the weight of the subtree rooted at $x_i$, i.e. the number of elements in the subtree rooted at $x_i$).

I was given the following argument but it doesn't quite make sense to me:

I can sort of see why a -1 would come in since $\frac{1}{2} = 2^{-1} \implies log(\frac{1}{2}) = -1$, but re-arranging the equation (and taking logs) gives:

$$ log(w[c]) - log(w[p]) \leq 1$$

which reverses the sign the wrong way. Plus, if you write down the details of the potential function change, things change inside the logs, which makes it tricky to analyze...


texts: Cognitive Computing vs Artificial Intelligence?

texts:
Can anyone please tell me the difference between them?
A brief definition of Cognitive Computing would appreciated.

Also how does cognitive computing relate to neural networks?


texts: Determining Language from Context Free Grammar

texts:
I am trying to understand how to write the language given the predicates of the context free grammar. As an example, I have the following grammar:

$S \to 0B \mid 1A$

$A \to 0 \mid 0S \mid 1AA$

$B \to 1 \mid 1S \mid 0BB$

What this says to me is that the first symbol can be either a 0 or 1, and the  next could be 0 or 1 or 1 or 0, and you continue down the parse tree from there.
How does one determine what the language of the grammar is? I having trouble putting the patterns of symbols into a language definition.


texts: Can we easily check if we can place two not-intersecting circles inside a convex polygon

texts:
We have given convex polygon of $N$ vertices, and two circles of radius $r$. Is it possible to check if we can place those two circles completely inside the polygon, such that they don't intersect, but they might have one point in common.

For example if we have given square with sides of length $1$, and $r = 0.25$. Then the answer should be yes, as we can place those two circles.


texts:
I have read few research papers in which given a graph $G$ where $V$ denotes its vertex set and $E$ denotes its edge set. Model of computation is word RAM. "Without loss of generality assume that vertices are numbered from $1$ to $n$"

Question : How to justify the above mentioned assumption? I am not getting why this assumption is valid?


texts: Can g(n) be same for big O and omega notation for f(n)

texts:
I have been studying asymptotic notation and I understand that in big O notation $f(n) <=c1*g(n)$ and in omega notation we have $f(n)>= c2*g(n)$ where $c1$ and $c2$ are some constant.

Now I was wondering if the function $g(n)$ here are the same and the big O and omega of $f(n)$ is determined by constants $c1$ and $c2$. Or if the $g(n)$ is different for O and omega.

If $g(n)$ is indeed same can anyone explain with example how is it possible as I can think of the examples in which $g(n)$ is different in both cases.


texts: Do theorem provers demonstrate their own correctness?

texts:
I am not very well-versed in the world of theorem proving, much less automated theorem proving, so please correct me if anything I say or assume in my question is wrong.

Basically my question is: are automated theorem provers themselves every formally proven to work with another theorem prover, or is there just an underlying assumption that any theorem prover was just implemented really really well, extensively tested & reviewed, etc. and so it "must work"?

If so, does there always remain some underlying doubt in any proof proven by a formally verified automated theorem prover as the formal verification of that theorem prover still lies on assuming that the non-formally verified theorem prover was correct in its verification of the former theorem prover, even if it might technically be wrong - as it was not formally verified itself? (That is a mouthful of a question, apologies.)

I am thinking of this question in much the same vein as bootstrapping compilers.


texts:
Every theory has axioms and theorems derived from axioms.

How many axioms are there for automata theory? What are the axioms of automata theory?


texts: Non-trivial difference(s) between Computer Algebra System and Proof Assistant

texts:
Disclaimer: I am not even an expert user of these two kinds of software.
I understand that the trivial difference between proof assistants and CAS is that in proof assistants, the goal is to show that the given proposition reduces to a tautology. Whereas CAS are used to perform various transformations on mathematical expressions to find results that are useful.
When we are doing mathematics on paper, the techniques used while deriving something are not all that different from the techniques used while proving something. In each case, we start with an expression, and apply one (previously established) rule after another, until we reach our goal. As far as I know, the rules that are applied in derivations are exactly the same as the rules applied while proving something. Looking at it in another way, the human skills honed on derivations are perfectly applicable while performing proofs.
When comparing computer systems, the list of computer algebra systems has no titles in common with the list of proof assistants. From my lay perspective, to name a specific example, I think we can use CAS to derive the roots of a generalized quadratic equation, but only when we have the formula, can we use a proof assistant to verify it.
So, given the vast amount of mathematical knowledge encoded in the libraries of both CAS and proof assistants, why can't we use a CAS to perform proofs, and why can't we use proof assistants for deriving anything beyond tautologies?


texts: Explanation of Heavy light decomposition

texts: Can anyone explain heavy light decomposition of trees or give a resource to read it from? I have already gone through http://ipsc.ksp.sk/2009/real/solutions/l.html which is the best i could find but still could not understand its working completely.


texts:
I have the following the statement and I have to prove whether it is true or not.

Given a planar and Hamiltonian graph $\mathbb{G} = (V, E)$, show that we can partition $E = E_1 \cup E_2 = E$ so that $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ are both connected and outerplanar graphs.

I have tested the statement for few graphs and it seems correct to me, but I am not sure how can I use the property of the Hamiltonian cycle to decompose the graph into two sub-graphs.
I appreciate any hint!


texts: How to improve the CPI and Speed up factor in CPU-OS simulator?

texts:
I am using the CPU-OS simulator by Besim Mustafa(https://www.merlot.org/merlot/viewMaterial.htm?id=476196) and I am studying Pipeline Stages. I have written a simple program and captured the metrics like CPU Clocks, CPI, Instruction Count, Speed Factor.
My question is what changes should I make to improve the CPI and Speed Factor.


texts: Robust two lines/segments intersection point in 2D

texts:
Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide).

There is a Wikipedia article which gives us exact formulas, but there are two of them: one that uses t ratio and approaches intersection point from first line segment and the other -- uses u and the second line segment. How can I select which one to use in my scenario?

For example: my initial implementation which always used t failed on

first_segment = Segment(start=Point(x=-5, y=0), end=Point(x=72057594037954921, y=0))
second_segment = Segment(start=Point(x=0, y=0), end=Point(x=0, y=3))

gives

Point(x=5.921189464665284e-16, y=0.0)

which is incorrect, but when I switch to use u or change order of arguments it gives me correct

Point(x=0.0, y=0.0)

So my question is: is there robust way to calculate intersection point?


texts: Maximum number of nodes connected when the link has a large buffer

texts:
A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream;when the source is on, the rate of traffic is 10 Mbps, and when the source is off, the rate of traffic is zero. The duty cycle,which is the ratio of on-time to off-time, is 1 : 2Assuming that all sources are synchronized and that the link is provided with a large buffer, the maximum number of sources that can be multiplexed so that there is no data loss is_____.

My solution manual claims that the max. no of nodes connected can be found out by dividing total link capacity from expected bandwidth utilization.

I dont understand why we need to take the expected bandwidth. Why can't we simply use the maximum bandwidth utilization?

Thanks in advance!


texts: Minimal basis for set of binary vectors using XOR

texts:
I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to find another set of binary $n$-vectors $B \subset \{0,1\}^n$, with minimal size $|B|$, such that every vector in $S$ can be expressed by the XOR results of some subset of $B$ (so $B$ is essentially a basis for $S$ using XOR instead of addition and allowing only binary coefficients in the linear combination).

In a way, this is a form of PCA for binary vectors. While searching for literature on this problem, I came across the Discrete Basis Problem also discussed in this PhD thesis, which seems closely related. Instead of XOR it uses OR, and here $|B|$ is an additional input (and the task is it to minimise the error in representing $S$ with vectors from $B$). This problem is NP-hard. Does the same apply to the problem I've presented above, or is there an efficient solution? Any pointers to existing literature would be much appreciated.


texts: Language theoretic comparison of LL and LR grammars

texts:
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how is the situation really? In particular, I am interested in how LL(*) fits in.

As far as I know, the respective sets of grammars LL and LR parsers accept are orthogonal, so let us talk about the languages generated by the respective sets of grammars. Let $LR(k)$ denote the class of languages generated by grammars that can be parsed by an $LR(k)$ parser, and similar for other classes.

I am interested in the following relations:

$LL(k) \overset{?}{\subseteq} LR(k)$
$\bigcup_{i=1}^{\infty} LL(k) \overset{?}{\subseteq} \bigcup_{i=1}^{\infty} LR(k)$
$\bigcup_{i=1}^{\infty} LL(k) \overset{?}{=} LL(*)$
$LL(*) \overset{?}{\circ} \bigcup_{i=1}^{\infty} LR(k)$

Some of these are probably easy; my goal is to collect a "complete" comparison. References are appreciated.


texts: What can be said about Θ-classes in m and n if we know that m < n?

texts: A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it is $\Theta(n^2\log n)$?


texts: Convert conjunctive normal form to equivalent boolean formula with only NAND gates

texts: Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause).  I want to convert it to an equivalent boolean formula that uses only NAND gates with fan-in 2, without introducing any new dummy boolean variables. I'm wondering how much this will increase the size of the formula. If $\varphi$ has size $n$, how large does the resulting formula need to be? Can I convert $\varphi$ to an equivalent formula with only NAND gates that has size $O(n)$? If $O(n)$ isn't achievable, what's the best that is?


texts: How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?

texts:
Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform the worst-case time complexity analysis for this algorithm?
The context in which this question came about is when I was going through the analysis of MAX-HEAPIFY algorithm given in CLRS(3rd edition) on page 154. In the worst-case analysis, the author had assumed some arbitrary input size $n$ and then concluded that the worst case occurs when the bottom-most level of the heap is exactly half full. This threw me off since in various texts and articles, $n$ is assumed to be fixed when performing the worst case analysis(and even for best or average cases for that matter) and that the number of elements at the bottom-most level of a heap of $n$ nodes is fixed. In that light, I concocted this algorithm so as to have the worst case dependent on $n$.
My intuition tells me that the worst case time complexity for this algorithm is $\mathcal O(n^2)$ since that's the worst case runtime for Bubble Sort. But I want to know the precise mathematical formulation of the worst-case time complexity analysis for any algorithm. Any insight would be much appreciated.


texts: What is the Space Complexity of Tail Recursive Quicksort?

texts:
Looking at the following tail recursive quicksort pseudocode

QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
         // For the first call lo = 1 and hi = n
Output: The array A in sorted order

If lo = hi return
         // The array A is already sorted in this case
If lo > hi or indices out of the range 1 to n then return

Else
      Pick an index k in [lo,hi] as the pivot
              // Assume that this can be done using O(1) cells on the stack
      i = Partition(A[lo, ..., hi], k)
              // Use in-place partitioning here so assume that this can be done
              // using O(1) space on the stack

If i - lo <= hi - i
      QuickSort(A, lo, i-1) // sort the smaller half first
      QuickSort(A, i+1, hi)
Else
      QuickSort(A, i+1, hi) // sort the smaller half first
      QuickSort(A, lo, i-1)

Assuming that the pivot is chosen adversarially each time I analyzed that it should have a space complexity of O(logn) [which I am not entirely sure is correct], but how would the space complexity be affected if the pivot is then chosen uniformly at random? I am fairly new to understanding space complexity over time complexity, so any feedback is appreciated!


texts: What is the difference between $AC^2$ and $FO (\log \log n)$ complexity classes?

texts:
$FOLL$ or $FO (\log \log n)$ is a complexity class of all problems solvable by uniform poly-size circuit families of unbounded fan-in and depth $O(\log \log n)$.

$AC^2$ is a complexity class of all problems recognized by boolean circuits with depth $O(\log ^{2}n)$ and polynomial number of unlimited fan in AND and OR gate.

  Question. : What is a difference between $FOLL$ and $AC^2$?

In the definition of $FOLL$  they have used "uniform " poly-size and in the definition of $AC^2$ they are saying boolean circuits.


texts: Trustless exchange without a third party

texts:
Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other? For example, Alice and Bob have Y and X objects (some information) and want to exchange them (in other words both Alice and Bob after transaction will have access to the set Y∪X). How can they do this directly to each other?
Is it possible to solve this problem, for example, using private keys, zk-proofs, etc? Is it possible to solve it in principle?
Thank you!


texts: Seeking "gold standard" to evaluate accuracy of network clustering algorithm

texts:
I'm currently looking at network clustering algorithms (we're currently looking at both directed and undirected, unweighted networks).  The algorithms we've tried produce visually nice clusters.  However, we would like to evaluate them against some "gold standard" -- a collection of networks in which the clusters have already been identified (and are more-or-less regarded as the clusters by the complex network's research community).

  Question: What are the gold standards for network clustering algorithms?  Where can I access them?


texts: How to find how many times an object's path crosses another?

texts:
I have several hundred objects that will move in a fixed area throughout the day.  Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a few seconds or minutes, the time window tolerance.  How can I determine how many times that happens throughout a fixed period of time, let's say in a day?

For example, to visualize it on a simple level, let's say I have 2 points, A & B, arranged in a north-south and east-west configuration:

         (A) - Loc 1

              |
              |

Loc 3---------------------- (B) Loc 4

              |
              |
            Loc 2

Object A moves only from Loc 1 to Loc 2 throughout a given period of time.  Likewise Object B only moves from Loc 3 to Loc 4 during that same period of time.  They cross paths at the center.  One could just calculate the speed of A and figure out when it hits the location of the path cross, and also do that with B.  Then simply determine when those cross point time windows are close.  However that logic breaks down when I have hundreds of objects, variable indirect paths, and changing speeds.

What I am given at the end of the day is the path of each object, timestamps along the path, stops and times.  Is there a straightforward way or algorithm to determine how many times one path crossed another during a time window tolerance?


texts: Collision resistant Hash function in chaos cryptography

texts:
In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat theoretically chaos based cryptography. It is still an active area of research with advantages and disadvantages.

How can I prove that the has collision is minimum or collision resistance for any chaos function used for chaos based cryptography, where the chaos map is the hash function?

An algorithm to achieve cryptography hashing is the chaos based cryptographic hash function which indexes all items in hash tables and searches for near items via hash table lookup. The hash

table is a data structure that is composed of buckets, each of which is indexed by a hash code.

Two hash codes for two different messages can collide if they have the same hash code. This is often called the Birthday paradox.

The properties of a good hash function is
that there should be no hash collision. This property also holds for Locality sensitive hashing where a hash function is used  to search for the approximate nearest neighbor.

How can I proof this statement for chaos based hashing in cryptography? If the hashing function is a chaotic map, $f()$, then how to show the expression of collision probability? Please help.