texts: What is the underlying pattern/rule in this question?

texts:
I can't find a concise algorithm for the following coding problem:

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.You can assume that the messages are decodable. For example, '001' is not allowed.

I've recognized that any number <=26 can be represented 2 ways. I've tried to observe what happens when I add a number like 2, which can later form another 2-digit number with the one after it (e.g. 22 - 2 combinations, 222 - 3, 2222 - 5, 22222 - 8). But I can't seem to find a robust pattern.

This was a coding interview question that was supposed to last 30min, so I'm embarrassed I can't see the latent rule.


texts: What is the different between Dijsktra's algorithm and KNN?

texts:
I am implementing machine learning software and in my case, I am using K-nearest neighbour classifier to get the task done.

So far, I am trying to understand how Dijkstra's algorithm that has been used to solve salesman travel problem is different from K-nearest neighbour algorithm?


texts: What is the complete version of the paper: "How to Generate and Exchange Secrets (extended abstract)" by Andrew Yao?

texts:
I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. However, I can only seem to locate the extended abstract which lacks proofs and does not seem to mention garbled circuits. It only appears to define useful properties for solving the problem and state several theorems without proof. A complete version of the paper is mentioned at the end of this extended abstract, but I cannot locate it. Is the complete version under a different name?

I have already found expositions that explain garbled circuits. At this point I am interested in finding the complete paper, if possible.


texts: Example of a code that can be decoded using bounded distance decoder

texts:
In the book Information theory, Inference and Learning Algorithm, in chapter 13, MacKay defines bounded distance decoding

  A bounded distance decoder is a decoder that returns the closest codeword to a received binary vector $\mathbf{r}$ if the distance from $\mathbf{r}$ to that codeword is less than or equal to $t$; otherwise it returns a failure message.

Could anybody provide an example of a simple linear code that can be decoded by such a bounded distance decoder?


texts:
Consider the following schema:  Students(Id, Name, AdvisorId, AdvisorName, FavouriteAdvisorId)

What are the functional dependencies here? Ir seems that it would be:

 Id --> Name AdvisorId AdvisorName FavouriteAdvisorId

If we know the student id then we know his name, his advisor, his advisor id and his favouriteadvisorid. But the correct functional dependencies given are:

 Id ---> Name FavouriteAdvisorId

 AdvisorId ---> AdvisorName

Why is this?


texts: Arc-Length parameterization of a cubic bezier curve

texts:
I like to implement an arc-length Parameterization of a cubic bezier curve. So far I have implemented the method of calculating the arc length of the curve and now I'm stuck at calculating the times to divide the original curve into equal arc length segments.

What i have:

$m = 5$ The number of segments to create
$i = 0,1, ...., m$
$s = \text{arc length}$
$l = s / m$
$t_0,t_1,...,t_n$ The parameter values of the original bezier curve.

The formula I have:
$$\int_{t_0}^{\tilde{t_i}} ds/dt = i * \tilde{l}$$

To calculate the value of $\tilde{t_i}$ I would have to go through 2 steps:

Calculate a spline segment indexed by $j$ which satisfies $\sum_{p=0}^{j-1} l_p \le i * \tilde{l} < \sum_{p=0}^{j}l_p$
Compute $\tilde{t_i}$ such that $\int_{t_j}^{\tilde{t_i}}ds/dt * dt = i  * \tilde{l} - \sum_{p=0}^{j-1}l_p$

To my questions:

What is $\tilde{l}$? I know it is an approximated value but is it neccesery to be different or could just use $l$?
The first calculation of $j$ makes sense, but how would I solve the second to $\tilde{t_i}$?

Maybe I just don't understand correctly what the integral $\int_a^bds/dt*dt$ is or how I can calculate it programmatically.

I am following this paper.


texts:
let's have these two languages in the alphabet $\{a,b,c\}$:

$L_1 = \{ w \mid w \text{ is a palindrome and $|w| < 200$}\}$

$L_2 = \{ w \mid w \text{ is a suffix of $u$ and $|u|$ is a prime number and $u$ doesn't contain a $c$}\} $

and I have to prove that $L_1 ∪ L_2$ is regular.

So my idea is I have to prove both languages are regular and therefore their union would be regular. $L_1$ is obviously regular since it's finite. I also know that the language consisting of all suffixes of words from a regular language is also regular, so I narrowed it down to proving that

$L = \{w \mid |w| \text{ is a prime number and $w$ doesn't contain a $c$}\}$

any ideas on that one? Thanks in advance.


texts: Macro expansion is done in which phase of a compiler?

texts: This is question raised by my teacher in the class room. I don't have enough knowledge about phases of compiler and macro expansion. Could someone help me in finding out proper solution to this


texts:
Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative element in each $f$ mapped pairs. For example $g(x)=\min (x,f(x))$ $$g: S \rightarrow \tilde S \subseteq S$$

I want to build a compact lookup table from $g$'s codomain $\tilde S$ to any problem data, taking $|\tilde S| \leq |S|$ cells in memory. Ideally I wish to construct a bijective mapping $\tilde S \rightarrow \left[0, |\tilde S| \right[$.

Can it be done efficiently in general (without hash map or scanning) ? What properties of the involution $f$ could help with that ?

Edit: I formulated the problem in the more general/formalized, hoping for a generic solution. Following D.W.'s comment, I'll give a concrete application:

I work with DNA words of $k$ nucleotides bases called $k$-mers. Since there is four bases, $k$-mer are represented as elements of $S=[0,2^{2k}[$

However DNA can be read on both strands, with opposite orientations and complementary bases ($A \leftrightarrow T$, $G \leftrightarrow C$). Going from one strand to the other can be represented by this involution (reverse-complement, here for 5-mers): $$ f(x) = \text{reverse}_2(x) \oplus 0\text b1010101010 $$ where $\text{reverse}_2(abcdefghij)=ijghefcdab$ inverse the order of 2-bits blocks and $\oplus$ is the bitwise XOR.

Since many applications don't distinguish between a $k$-mers and its reverse-complement, a canonical $k$-mer is picked with $g(x)=\min (x,f(x))$. The cardinality of $g$'s co-domain is: $$
\left|\tilde{S}\right|=\begin{cases}
2^{2k-1} & \text{if }k\text{ is odd}\\
2^{k-1}\left(2^{k}+1\right) & \text{if }k\text{ is even}
\end{cases}
 $$

In practice saving less than one addressing bit is not worth a complex solution. But cache locality is a good thing to have. $g$ can be chosen differently if it help with that.


texts: What to do following a reduce in LR(1) parsing?

texts:
I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what will the current state be? It seems like it could be both State 0 or State 3 (since state 3 loops back on itself on the lookahead c), i.e the GOTO of C from either state 0 or state 3. I am confused on states like 3 that loop into themselves.
The grammar is this:
$$S'  \rightarrow  S $$
$$S  \rightarrow  CC $$
$$S  \rightarrow cC $$
$$C  \rightarrow d $$

Question 1 : When the machine is at state 3. On encountering d as a lookahead, what is the action, and the new state?
Question 2 : At a more fundamental level, what do you do following a reduce in any kind of LR parsing. You can't stay in that state itself, and have to go somewhere else right? How do you make that choice?
Edit: I made a small mistake in the grammar productions. I had originally included the grammar C -> c which was a mistake, and was removed.


texts: How is this problem related to the study of algorithms and big O notation?

texts:
I'm taking a graduate computer science course on algorithms and analysis. The current subject is big O notation and recursion. How is the following problem related to the study of algorithms, recursion, and big O notation? I know and understand the solution to the problem, but I just don't see how this is relevant to the subject matter.

Given an $x$, show that $x^{62}$ can be computed with only eight multiplications (A general algorithm can not accomplish it).


texts:
I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero.

$$
\lim_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}}
$$

But I'm not sure how I can reduce this expression.


texts: Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms

texts:
From my understanding, a problem amenable to a dynamic programming solution has these two properties:

Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps reappearing. Thus, memoization can be used to boost performance.
Optimal Substructure — The problem can be broken down into smaller components, which can then be solved independently and the results combined to produce the answer to the overall problem. This allows for subproblems and possibly overlapping subproblems.

I've read that Bellman-Ford and Floyd-Warshall are dynamic programming algorithms, but how do I think of them in terms of the two properties given above?


texts: Prove that $\text{EXACT-TRIPLE}$ is not in NP

texts:
I received the following assignment:

$\text{EXACT-TRIPLE} = \{ \phi \mid \phi \text{ is a boolean formula that has exactly 3 satisfying assignments} \}$.

I need to decide whether this problem belongs to NP or not. I assume it does not. How do I prove that?


texts: Multiple production rules for expressions of the same type?

texts:
I often see syntax like

expression = term | expression, "+" , term;
term       = factor | term, "*" , factor;
factor     = constant | variable | "(" , expression , ")";
variable   = "x" | "y" | "z";

You see, all the rules produce an arithmetic value. Each can replace the other. Why not just declare

aexpr = var | num | (expr + expr) | expr * expr;

?

Certainly I need different production for expression of different type

statements = "if (" bexpr ") body | "while (" bexpr ")" body | a_variable "=" aexpr
bexpr = (bexpr "|" bexpr) | bexpr "&" bexpr | aexpr ">" aexpr

Here, I introduce a new production rule (a line per rule) only when I get a new type of expression and see no reason to split them.

I just started to generate random sentences and see that expressions are naturally grouped according their result type (e.g. arithmetic and boolean are different) and that is all. If you need an arithmetic expression, you draw (rewrite) it from arigthmetic pool, if boolean form the boolean pool. Why to split the pools into further groups?


texts: Getting negative cycle using Bellman Ford

texts:
I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name it.
How can I get the actual path $v1, v2, \ldots vk, v1$ of the cycle?
After applying the standard algorithm we already did $n-1$ iterations and no further improvement should be possible. If we can still lower the distance to a node, a negative cycle exists.
My idea is: Since we know the edge that can still improve the path and we know the predecessor of each node, we can trace our way back from that edge until we meet it again. Now we should have our cycle.
Sadly, I did not find any paper that tells me if this is correct. So, does it actually work like that?
Edit: This example proofs that my idea is wrong.
Given the following graph, we run Bellman-Ford from node $1$.

We process edges in the order $a, b, c, d$. After $n-1$ iterations we get node distances:
$1: -5$
$2: -30$
$3: -15$
and parent table:
$1$ has parent $3$
$2$ has parent $3$
$3$ has parent $2$
Now, doing the $n$th iteration we see that the distance of node $1$ can still be improved using edge $a$. So we know that a negative cycle exists and $a$ is part of it.
But, by tracing our way back through the parent table, we get stuck in another negative cycle $c, d$ and never meet $a$ again.
How can we solve this problem?


texts: Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?


texts: Language of all words of the form $ww$ is in $\mathsf{NTIME}(n)$

texts:
Show that the language $\{ ww \mid w \in \{0,1\}^* \}$ is in $\mathsf{NTIME}(n)$.

I have a doubt first of all how can I prove that. Secondly, what does NTIME mean? Can we use a $k$-Tape Turing machine, when they say NTIME OR NSPACE?
What do both of them mean?


texts: Expressing partial decidability using existential quantification

texts:
def.
A predicate M(x,y) is partially decidable if the function f given by " f(x,y) = 1(if M(x,y) holds), f(x,y) = undefined(otherwise) " is computable.

Thm.
If M(x,y) is partially decidable, then so is the predicate ∃yM(x,y).

proof.
 Take a decidable predicate R(x,y,z) such that M(x,y) iff ∃zR(x,y,z).
Then...

I can not imagine the R(x,y,z)...
Please explain the way of thinking.

( Page115, Computability by Nigel Cutland)


texts:
What would be the line by line analaysis and construction function T[n] with Big Oh notation?

Thanks a lot.


texts: How to simulate natural number in Pi Calculus

texts:
I have some questions about Pi Calculus:
How to simulate the natural numbers only with its primitives?
It's possible simulate the if else clauses without the sum (+)?
A minimal and standart example would be interesting.


texts: What do we know about NP ∩ co-NP and its relation to NPI?

texts:
A TA dropped by today to inquire some things about NP and co-NP.
We arrived at a point where I was stumped, too: what does a Venn diagram of
P, NPI, NP, and co-NP look like assuming P ≠ NP (the other case is boring)?

There seem to be four basic options.

NP ∩ co-NP = P

In particular, co-NPI ∩ NPI = ∅
NP ∩ co-NP = P ∪ NPI

In particular, co-NPI = NPI?
NP ∩ co-NP ⊃ P ∪ NPI ∪ co-NPI

A follow-up question in this case is how NPC and co-NPC are related;
is there an overlap?
Something else, that is in particular some problems from NPI are
in co-NP and others are not.

Do we know which is right, or at least which can not be true?

The complexity zoo entries for NPI and NP ∩ co-NP do not inspire much hope that anything is known, but I'm not really fluent enough in complexity theory to comprehend all the other classes (and their impact on this question) floating around there.


texts: Storing variable length Keys in hash table itself

texts:
I wrote a custom hash table for a project I'm working on. The core functionality was pretty simple rolling table:

In each table there is a memory section for HashItemReference(integer SecondHash, integer ItemN) which is the actual table part and a list of HashItem(integer Value, string Key)
Each HashItemReference would contain a second hash of the original key and a number to refer to the hash item
When looking for an item, it would land on the first hash position as usual and then go sequentially, checking if the second hash checks out then check the actual hash item. (The table lives on a spinning disk, this was necessary to minimize jumping around and keeping it sequential)
If the actual key(variable length string) checks out then return the number associated with this key.

This approach works well enough all though it does have one hypothetical problem - If the average size of the keys was unknown(which in this case it isnt), it would be difficult to make the memory reserve for hash table and the list of items fill up at the same time, leading to either wasted space(which in case of hash tables directly translates to wasted performance) or more resizing(even worse).

I don't have the time to test things right now but nearing the end, I got another idea, I wonder if anybody has built something like that and can comment on how it compares to the solution above.

The idea:

Instead of storing the hash items in a separate list, cut them to chunks and store sequentially in the actual table.
This would need a header to indicate continuation or new item so something like 1B (New or Old) + 7B of data (sequentially first name and then value).
Since there is no way to stitch together fragmented chunks they would have to be strictly sequential so when inserting into the table, an empty sequence long enough would have to be used.
The header byte could also contain more information, for example, how many chunks to skip. It wouldn't know how far off the desired block will be but it knows its own length and I could skip at least that (or a maximum of 128) before checking another chunk.

This approach would completely eliminate the issue with the previous approach but I'm a bit skeptical about sticking unfragmentable chains of blocks into a table ruled by a function whose whole purpose is to fragment as much as possible.

So.. thoughts?


texts: What algorithms are there for scheduling tasks

texts:
The scenario is something like this

I have tasks that get requested, with a category and a priority
For simplicity let's assume that rate of incoming tasks and completion is about the same, with some existing backlog of tasks
Each category of tasks can only be completed at some certain rate
Completion of tasks is handled out of the system, so we can assume that deciding to take on a certain task is equivalent to completing it

So I want some way of deciding which tasks to complete at a given time, given the existing tasks and their priorities, and the limits on completion within a certain category

One greedy algorithm would be to just organize each category by priority, and then at each decision point take in as many tasks as is allowed by that category's rate, but the problem with this is that if a lot of high priority tasks come in low priority tasks will just sit in the backlog, potentially forever.

I've looked at some scheduling concepts like round robin scheduling and multilevel priority queues, but they don't seem to fit what I want - tasks can't be paused/rescheduled as in round robin, and multi priority queues seems like it'd still have the problem of getting to low priority tasks (could just make the priorities more stratified, but then it's just back to the original problem with deciding how many tasks to take from each queue)

Any advice on what I should look into? Maybe it's a sort of "repeated knapsack" thing?


texts: Using Queues for a Stack and Stacks for a Queue

texts: I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to start.


texts: Clock synchronization in a network with asymmetric delays

texts:
Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$.

The simple method is that the computer sends a query to a time server, noting the local time $B + C_1$. The time server receives the query at a time $T$ and sends a reply containing $T$ back to the client, which receives it at a time $B + C_2$. Then $B + C_1 \le T \le B + C_2$, i.e. $T - C_2 \le B \le T - C_1$.

If the network transmission time and the server processing time are symmetric, then $B = T - \dfrac{C_1 + C_2}{2}$. As far as I know, NTP, the time synchronization protocol used in the wild, operates on this assumption.

How can the precision be improved if the delays are not symmetric? Is there a way to measure this asymmetry in a typical Internet infrastructure?


texts: Why is it most efficient to resize a dynamic array to 2 * array.length()?

texts:
By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array.

I read in a textbook that doubling the size of the array is the most efficient resizing. I want to know if this is in fact demonstrably true and not just a matter of personal preference.

We will want to minimize the amount of resizing events, because each such event requires O(n) time where n is the number of elements in the list.

We also should be careful not to make the list too big because it might be a waste of memory.

Why does the author of my textbook say that 2 * array.length() is the magic number?


texts: Boolean circuit size of $i$th bit of determinant?

texts:
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers.

Is there a polynomial size boolean circuit for $i$th bit of determinant and is it still logarithmic depth?


texts: Are there peer-reviewed papers studying the pros and cons of functional programming?

texts: Can somebody refer me to peer-reviewed papers studying the advantages or disadvantages of writing code in a functional style? Are there papers which discuss the applications of Lambda Calculus in fields such as Machine Learning, Language Design, etc.?


texts:
I am searching for information on a variant of the 0-1 Knapsack Problem I will call the Vector Knapsack Problem (VKP), which is basically the same as the standard KP except that the values being summed are vectors (and them sum is the Euclidean norm of the sum of the vectors). Formally, given a set of $m$ vectors $v \in \Re^{n}$, a set of non-negative weights $\alpha \in \Re_{0+}$, and a non-negative maximum Euclidean norm $W \in \Re_{0+}$,

$$Maximize: ||\sum_{i=1}^{m} v_{i}x_{i}||_{2}$$
$$S.T.:\sum_{i=1}^{m}\alpha_{i}x_{i}\leq W, x \in \{0, 1\}$$

What, if anything is known about the complexity of this problem? It seems like it should be NP-Hard at minimum (as a generalization of the 0-1 Knapsack Problem), but it is unclear to me whether the decision problem variant is NP-Complete.


texts: Which languages do Perl-compatible regular expressions recognize?

texts:
As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that allows to execute arbitrary code inside the pattern.

If you don't know what PCREs are, please read this and this.

The problem is, the resources available on internet pretty much stop at context-free languages, and PCREs can match more than those (see below); but I really don't know where to find more theorems or papers about this kind of stuff.

In particular: PCREs are obviously a superset of regular languages (as the PCRE syntax has all the regular language operators).

Any CFG can be put in Greibach normal form, which removes left recursion. I think this can be used by means of (?(DEFINE)...) groups to "translate" the grammar into matching subroutines, avoiding to choke on left recursion, by translating:

the non-terminal at the head of each production becomes a subroutine (?<HEAD>...)
the body of each production is put in the subroutine; terminals are left as-is, non-terminals become procedure invocations (i.e. (?&NONTERMINAL));
all the productions with the same nonterminal as head are ORed together by means of the | operator (plus additional grouping with (?:...), if necessary)
the pattern then becomes a (?(DEFINE)...) group containing all the "translated" productions, and an invocation for the procedure of the starting symbol, to match the entire string, i.e. ^(?(DEFINE)...)(?&START)$

This should deal with any CFG. Therefore, PCREs should be able to match any CFL.

There's more: let's take the simple language
$$L = \{ ww | w \in \Lambda^* \} $$
i.e. the language of the strings repeated twice. This language is not a CFL -- the pumping lemma for CFLs fails. (Pay particular attention that
$$ |vxw| \leq p$$
must hold, thus you can't just pump the beginnings or the ends of the two repeated strings.)

However, this language is easily matched by a PCRE: ^(.*)\1$. Therefore, we're strictly above CFLs.

How much above? Well, as I said, I have no idea. I couldn't find any resources about CSLs or all the other classes in between to make up my mind. Any expert willing to discuss this?

Addendum: I was asked to specify exactly which subset of the PCRE syntax must be allowed. As I wrote at the beginning of the post, I wanted to exclude any operator that allows to execute arbitrary code inside of the pattern, such as ??{}.

For the argument's sake, I think we can stick with the syntax defined by the pcresyntax(3) man page, which is a reasonable subset of what Perl 5.10-5.12 offers, minus the callouts (as they're not inside the pattern). I'm not sure that adding or removing backtracking control verbs change the language we can recognize; if so, it would be nice to figure out which classes we get with and without those.


texts: Coercing a list of nodes into the most probable tree

texts:
Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document structure is not made explicit (i.e., we have a linear flow of text). From the section headings, we wish to automatically determine the most likely document structure.

For titles on the same sectioning level, we know that they probably have the same kind of markup, and they probably increment in numbering, but we don't know exactly what they should look like (e.g., bold/italic; arabic/roman; how deep subsectioning goes), and their relatedness may be fuzzy (the author might forget a number in a sequence, for instance 1. First section, Second section, 3. Third section).

To make things more explicit, we can assume assume that we have a features vector fs with a fixed number of features, that combines linearly into a fitness function f(fs) = w₁ f₁ + w₂ f₂ … wₙ fₙ, given a weight vector ws. The fitness function is arbitrary, this is just to make the problem explicit.

So from list G:

We wish to create a tree G' such that:

G' maintains the preorder relations of G
G' maximizes some fitness function f(G'), where f calculates how alike nodes are that are children of the same parent (same markup; incrementing numbering).

(root not displayed)

My question: does this problem reduce to another well-known problem?

This problem reminds me of a lot of stuff I've seen before, from finding the best path through a DAG to hierarchical clustering, except nothing seems to hit the sweet spot in terms of describing or solving the problem.
I guess it's closest to the problem of finding the minimum spanning tree, except calculating the spanning tree score is not as straighforward.

I have thought of my own solution, but I was surpirised that I could find no resources that deal with this problem exactly.

My solution would be a dynamic programming algorithm that attaches a score to each possible tree as a linear function. (Meaning we can cache subtrees without re-calculating everything.) We can learn the constants of our function using some expectation maximization algorithm based on existing document structures.


texts: Finding N most distinct values in set given distance metric

texts:
Let's say you are given a set with $V$ vectors and you are given a simple Euclidean distance metric $d(a,b)$ for $a, b \in V$. Then what would be the most efficient algorithm to build a subset $S$ of a desired size $k$ such that the sum of the distances between the elements of the subset is maximized?

In other words, how does one find a subset with the most distinct vectors?

I have tried modeling this as a complete graph where the nodes are vectors and the edges the Euclidean distances between them, but I couldn't find a graph algorithm that solves this problem. It seems like finding an independent set of given size $|S|$ with the maximum number distance between them.


texts:
I am trying to find a fast algorithm that can compute the number of hamiltonian paths in an undirected graph. I saw this on the web, but it sounds like this finds all hamiltonian paths starting from one specific vertex. (for example vertex '0' in this code)
One idea is to run the above algorithm for all of the vertices as a starting point and then half the number of total paths to get the answer (because each path has $2$ starting vertices and by this approach, we are computing each path twice). I was wondering if there is a straight algorithm with backtracking which is faster than what I just mentioned above.
Also,if m is the number of edges in our graph, for simplicity assume that $m \leq \frac{1}{2} C(n,2)$


texts:
I hope I'm in the right section:

I know that if P = NP, then 3-SAT can be solved in P (Cook), but is the opposite valid, too? If P != NP, then 3-SAT is not in P?

Thanks!


texts:
I am learning DAGs and Equivalence Class of DAGs, I am reading the material by Prof. Campos Ibáñez here: https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/node2.html

However, I don't understand this:

  "It should be noted that each structure in the DAG space is not always
  different from the others in terms of its representation capability:
  if we interpret the arcs in a DAG as causal interactions between
  variables, then each DAG represents a different model; however, if we
  see a DAG as a set of dependence/independence relationships between
  variables (that permits us to factorize a joint probability
  distribution), then different DAGs may represent the same model. Even
  in the case of using a causal interpretation, if we use
  observation-only data (as opposed to experimental data where some
  variables may be manipulated), it is quite common for two Bayesian
  networks to be empirically indistinguishable."

Could any please explain your understanding about this part? What are the differences between causal interactions and independence/dependence relationship? I'm new and a little bit confused to this.

Your help is really appreciated!


texts: What does "no value is acceptable" in Machine Learning hypothesis representation

texts:
I am new to machine learning. I am reading the book, where I have:
– Most general hypothesis
< ? ? ? ? ? ? >
– Most specific hypothesis
< Ø Ø Ø Ø Ø Ø >

in
Sky AirTemp Humid Wind Water Forecast
< Sunny ? ? Strong ? Same>

I understand that for a learning instance, "?" means it can take on any value, so the outcome of the hypothesis would be 1, as long as the specific attribute is met.

I am confused about "Ø". The book says any value is unacceptable.

Does that mean, if a hypothesis is < ? ? ? ? ? Ø>, no matter what first 5 attributes are, since the last one is unacceptable, the outcome of the hypothesis will be 0?
If so, what is the difference between < ? ? ? ? ? Ø>, and < Ø Ø Ø Ø Ø Ø >?


texts:
I have a question about the details of microprogramming and hard wiring in CPU architecture.

in hardwiring, we write a code the compiler translates it to the ISA. then ISA is run in the hardware.

in microprogramming, we write a code the compiler translates it to the ISA(which is much more complicated than the ISA in hardwiring)then a device(I don't know the name) translates it to the hardware language.

am I correct?


texts: Formatting the names of optimization problems

texts:
Excuse me in advance if this is a off topic question, but I do not know in which other forum I can ask this question.
My question is of linguistic nature. What is the correct spelling of combinatorial optimization problems like the Max-Cut problem and the Exact Cover problem.
Should the initial letter be capitalized (Max-Cut)? Or shall all letter be capitalized (MAX-CUT)? Is it a matter of taste or are there strict guidelines one should follow?
The reason why I'm asking this is because I'm composing an article and I therefore would like to know if there is a consensus in the computer science community on the formatting of the names of optimization problems.


texts:
I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language

$$\{a^nb^nc^n\mid n\geq 1\}\,.$$

Can anybody tell me if this is a context free language? I can't make any context free grammar for it and I don't know any other proof.


texts: Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s

texts:
This is for formal-language-style regular expression and not about Unix-style regular expression.

I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings composed of only 0's, and doesn't accept strings composed of only 1's. The regular expression should only accept strings composed of 0's and 1's but without consecutive 1's.

Here's what I've seen so far: $(0+10)^*(ε+1)$

The problem is that it can accept empty string or just 1-character string 1. I would like to skip empty string and 1 since they are not strings of 0's and 1's.

I just couldn't find a good pattern. It seems that I have to create 2 regular expressions so that the first will be $(01+10)(0+1)^*$. If I am right, that will not accept empty string, will not accept just 0's, and will not accept just 1's. Then I would pass the result to the 2nd pattern $(0+10)^*(ε+1)$ to further validate that it has no consecutive 1's.

Could anyone explain what is the best solution to have the correct regular expression for strings of 0's and 1's?


texts: Algorithm to find if exists a k-length acyclic path with negative weight on an weighted undirected graph

texts:
Consider the following problem:
given an undirected graph with weighted edges (positive and negative) I would like to know if there is a k-length acyclic path with negative weight.
Is there an algorithm for that with a good complexity?
Maybe I can find the lighter k-length acyclic path and check if is negative, but it could be that this approach may have a bigger complexity.
Let me know what do you think.

(Sorry for the lousy english)


texts: NTP: synchronisation of time between two machines for ICMP timestamping

texts:
Some guy on the internet recommends using the same ntp server when it is required to troubleshoot asymmetric routes through ICMP, and it's somewhat important to have synchronised time between the two machines doing ICMP.

Granularity of timestamps in ICMP is 1ms (unique per 24h period), assume packet roundtrip between the source and destination of at least 100ms, each way of at least 50ms, plus jitter.

I find the recommendation of using the same ntp server unreasonable; for one, because it would seem that the likelihood of any given reliable ntp server, anywhere in the world, carrying correct time is much higher than the likelihood of transmitting said time through the internet over longer distances (plus with potential jitter and packet loss), e.g. a good collection of local servers is already the best you could do for the task at stake.

Basically, my conjecture is that, should a single ntp server be shared, it won't necessarily be a good server for both hosts doing ICMP, and would not contribute to the clock between the two (and only two) machines being the most synchronised, compared to a good collection of local servers instead.

What's the mathematical take on this?


texts: Partitioning millions of items into groups based upon a network of set similarities

texts:
So I'm working on a problem at work related to the matching of authors of millions of documents. I currently have minhash sets for each document's syntax (sets of 10 numbers with 8-10 digits each), however I need to figure out the most efficient way to partition the documents by their minhash sets so that I can simply compare the documents that have vaguely similar minhash sets. I've arrived at the following problem:

Given a collection of millions of sets, with each set containing 10 numbers of 8-10 digits, how would you go about partitioning the collection in that all sets in the partition have at least 4 elements in common with at least 1 other set in the partition? No item in any partition can share 4 or more set elements in common with an item from any other partition.

Basic example:

Given the sets of...

A={1, 2, 3, 4, 5, 6, 7, 8}
B={21, 22, 23, 24, 25, 26, 27, 28}
C={41, 42, 43, 44, 45, 46, 47, 48}
D={1, 2, 3, 4, 41, 42, 43, 44}

...we should have the the sets separated into 2 partitions:

Partition_1 = {A, C, D}
Partition_2 = {B}

This, however, needs to scale for tens of millions of sets instead of just 4.

I'm happy to provide more details and answer any questions. I hope my question was clearly worded. Thanks for your responses!


texts:
I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we want to sort).

Since inserting n items to a heap takes O(n) , and each delete-min takes O(d log n/ log d), I was thinking the bound is O(n d log n / log d). Am I right? If so, how do I prove that it is indeed a tight bound?

Thanks.


texts: When is the best time to include an ε-transitions in a NFA state diagram?

texts:
While doing my NFA homework in my automata class, I feel like I'm not taking advantage of the ε-transitions I'm learning about. I can solve problems without using it. It's not like I really need it, except for when an empty string is part of the language, then I'll finally add an ε.

A lot of my text book examples use it which is why I feel bad not including it in the homework problems. I started this NFDA topic (using the "Introduction to theory of Computation" book) about last week and a half ago. Maybe I should wait it out a little longer?

Or are there a few shortcuts I could be using in my diagrams I should know about? What are your criteria for including ε-transitions in your diagrams?

Thank you.


texts: Tree Languages are Word Languages on an Infinite Alphabet of Contexts

texts:
I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand.

In the beginning of Chapter 2, the authors want to show that regular string languages and regular tree languages have very much in common:

  We shall see [...] that many properties and concepts on regular word languages smoothly generalize to regular tree languages, and that algebraic characterizations of regular languages do exist for tree languages.

The sentence I don't understand then follows:

  Actually, this is not surprising since tree languages can be seen as word languages on an infinite alphabet of contexts.

How can I see a tree language as a word language on an infinite alphabet of contexts?


texts:
I have some "fuzzy" congruences like these:
\begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{2,3,4\},\\x&\equiv a_3 \mod 7 \text{ with } a_3 \in \{5,6\}\\ \end{align}
These example moduli would provide a unique solution for $x \mod lcm(3,5,7)$, if the $a_i$ were fixed.
Because the $a_i$ are not fixed, these "fuzzy" congruences lead to $2*3*2=12$ possible solutions for $x \mod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, there exists an additional condition, which provides an upper bound for $x$. For example:
\begin{align} x \mod lcm(3*5*7) &< 5 \end{align}

We can assume that all moduli $m_i$ are primes, f.e. $lcm(m_1,m_2,...) = \prod_i m_i$.
Furthermore each $a_i$ has at most $t$ possible values ($t=3$ in the upper example). Additionally, the possible values of $a_i$ are consecutive ($a_2 \in \{1,3,4\}$ is not allowed).
So the generic equations look like:
\begin{align} x&\equiv a_i \mod m_i &\text{ with } a_i \in U_i \text{ and } U_i \subset \{0,1,...,m_i-1\} \wedge |U_i| = t \wedge \\&&\forall i,j: |i-j|=1 \Rightarrow |U_i[i]-U_i[j]| = 1
\\ x \mod \prod_i m_i &< k \end{align}

Is it partical feasible to calculate one solution for parameters like $\prod_i m_i \approx 10^{1000}$, all $m_i < 100000$, $k \approx 10^{50}$ and $t \approx 50$?

I tried to use the Chinese Remainder Theorem Method to find a solution for x:

Set $M_i:=lcm(m_1,m_2,...)/m_i$. It holds $gcd(M_i,m_i)=1$.

Hence, we can use the Extended Euclidean algorithm to find 2 Integers $r_i$ und $s_i$, which fulfill $r_i \cdot m_i + s_i \cdot M_i = 1$.

Set $e_i:=s_i \cdot M_i$, then \begin{align} e_i &\equiv 1 \mod m_i \\ e_i &\equiv 0 \mod m_j, j \neq i\end{align}.

The number $x:=\sum_{i=1}^n a_i \cdot e_i \mod lcm(m_1,m_2,...)$ is a solution.

Now i tried to solve $(\sum_{i=1}^n a_i \cdot e_i \mod \prod_i m_i) < k$ with $minValue(U_i) <= a_i <= maxValue(U_i)$.

These equations can be formulated as an Integer Programming instance (add an additional variable for the mod Operation). I tried to use mathematica to solve these, but it seems unfeasible even for "small" parameters like $\prod_i m_i \approx 10^{50}$, all $m_i < 1000$, $k \approx 10^{2}$ and $t = 3$.

Is there a more efficent way to solve this?


texts: How will broadcast behave with a certain capacity?

texts:
I wanted to confirm something and will appreciate your help. Suppose we have three nodes called A,B and C. All are connected to a switch whose port supports 1 Gbps. Now suppose, Node's A network card is 100 Mbps while the the remaining have a 1 Gbps. Following are the constraints;

A can send B only with a maximum of 100 Mbps.
A can send C only with a maximum of 80 Mbps.

Now if I were to broadcast a 2 GB file;

It would reach B after approx 2.73 minutes.
It would reach C after approx 3.41 minutes.

Now even if I replace node A's network card with 1 Gbps with the same constraints, I would still get the same results. Have I got it right?


texts: How do global variables and automatic variables with the same name interact?

texts:
Suppose I define a global variable and I define an automatic variable within a function definition with the same name as the aforementioned global variable.

What would happen to the global variable if I altered the automatic variable within the function body?


texts: Is the statement "Control unit controls overall operations of computer." true or false

texts: I was tutoring a grade 4 student about CPU and I got confused as there are also the other units of a cpu like arithmetic and logic unit and memory unit. So, is the above statement actually true even if ALU is the one which does the arithmetic and logical operations?


texts: Proof by induction over rules for mutually recursive relations

texts:
Consider the (big-step) semantics of a language ($a, e$ terms, $v$ values), defined by two mutually recursive relations, $\downarrow$ and $\Downarrow$, given by a set of rule-schemata (simplified):

$\frac{a \cdot x \Downarrow e ~~ e \downarrow v}{a \cdot x \downarrow v}{\tiny PROJECT} ~~~~~~~ \frac{a \downarrow \{ \ldots x = e \ldots \}}{a \cdot x \Downarrow e}{\tiny{FLAT}}$

If I want to prove something about this semantics, I would naturally use induction over rules or judgements. However, when I arrive at rule
PROJECT, I would have to make an assertion about $\Downarrow$. And to do so, I would have to return to $\downarrow$.

Is it legit to just merge the proofs for both relations and assume the induction hypothesis for $\Downarrow$ when dealing with $\downarrow$?
Is there some clean way to not merge the proofs but deal with them separately (something similar to break the recursion of functions)?


texts: Show how lack of universe levels would create contradiction in homotopy type theory (in Agda)

texts:
The homotopy type theory book claims in section 1.3 that "As in naive set theory, we might wish for a universe of all types" but from this one could "deduce from it that every type, including the empty type representing the proposition False, is inhabited"

The reference that it gives uses notation that I don't understand, however.

Could someone write invalid Agda code which produces a element of $\bot$, but which would be valid if Agda had a single universe that contains itself?


texts: How to avoid column wise access in matrix multiplication?

texts:
I know when we access elements  in rows it will be much faster than if it is accessed column wise. In matrix multiplication one of the matrices must be accessed column wise.
In GPUs with CUDA/OpenCL I could resolve this issue by explicitly copying both matrices row-wise into user-managed shared(cache)-memory (or local memory in OpenCL), and then can access data for matrix multiplication in anyway- no penalty for column access.

My question is how do I avoid such column access if I am implementing Matrix-multiplication on CPU, where I do not have any access to such shared memory as in GPU?


texts: Removing hidden ambiguity in grammar using left factoring

texts:
I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new non-terminal characters for the same.

For example,

<assignmentstats>------- <type><id>=<E>/ id=<E>/id'['<E>']'=<E>/

is transformed to

<assignmentstats>------- <type><id>=<E>/ id<LF3>
<LF3>------- =<E>/[<E>]=<E>

After applying such rules for all the required statements, I expected an unambiguous grammar.

But the following statement is somehow still ambiguous.

<body>------- <forrelatedstuff>/ <floors>/<stats>

Here are the related statements of the grammar(only those required has been shown)

<funcbody>----- {<stats>}
<stats>----- <stat> <stats>/ #
<floors>-------- <floor><floors>/ #
<floor>------- floo <id><arr>{stats}/id<arr>{<stats>}
<stat>----- <superstats>/<returnstats>
<superstats>----- <type>id<Zip>/id<LF3>
<building> ------- build <id> {<body>}
<returnstats>--------- return <E>

I looked more into it , and found that the ambiguity is between 'floors' and 'stats'. The first('stats') and first('floors), i.e. the set of first terminal characters contain 'id' and '}' for both.

I can see why this would be a problem and how left factoring could solve this. How can I remove such kind of ambiguity through left factoring?

Note: Here,
'id' denotes an identifier.

'#' denotes epsilon.


texts: Find at least $k$ paths with reward at least $\gamma$

texts:
The problem

Suppose we have a simple graph $G = (V,E)$, edge weights $c: E \to \mathbb{R}_+$ and node rewards $w: V \to \mathbb{R}$.

Given an integer $K$, positive scalar $B$ and a scalar $\gamma$, I would like to find a set of up to $K$ paths (either simple or not, whichever is easier to compute) such that the cost is less than the budget:
$$\sum_{e \in \rho_k} c(e) \le B$$
and the rewards accumulated are at least $\gamma$:
$$\sum_{v \in \rho_k} w(e) \ge \gamma$$
and if no path exists, return an empty set.

My question is three-fold:

This is NP-hard, right? If we could solve this problem, I think one could use it with a binary search to find the maximum weight path.
What assumptions on the graph would make this problem reasonable/easier to solve (hopefully more general than a tree)?
Is there a mixed integer approach (or something similar) to enumerate paths with these constraints?

Some context

I want to solve this problem as a sub-routine for a submodular set cover algorithm, FastCover, where items in the set are paths in the graph $G$. This gives me a lot of lee-way about how to define $G$, which is why I am interested in particular types of graphs which will make this problem easier.


texts: Are regular languages closed under such an operation?

texts:
Given a string, take all of its substrings (including the empty string). For example,  given $abc$, we can form a set $\{\emptyset, a, b, c, ab, bc, abc\}$.

Given a regular language, take all the substrings of each of its strings, and form a language thereof. I wonder if the formed language is still regular?

Btw, is there a name for such an operation?
In some sense, it is similar to taking the powerset of a set.

Thanks.


texts: Irregularity of $\{0^x1^y : y \nmid x\}$

texts:
The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.
How would one prove this using Pumping Lemma?
I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is necessary I'd imagine.


texts: Find a path that contains specific nodes without back and forward edges

texts:
I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For example for set = [1,3,4] the following path is acceptable:

but for the same set of nodes the following paths are not acceptable:

and

First of all i thought that it would be a good step to write bfs code for finding the nodes that i can visit from a specific starting node. Here is my code:

def bfs(G, s):
    q = queue.Queue()
    visited = []
    #Put s onto a FIFO queue
    q.put(s)
    #mark s as visited
    visited.append(s)
    #Repeat until the queue is empty
    while not q.empty():
        #remove the least recently added vertex v
        v = q.get()
        #for each unmarked vertex pointing from v:
        #add to queue and mark as visited
        for node in G.neighbors(v):
            if node not in visited:
                q.put(node)
                visited.append(node)
    print(visited)

Does anyone have any idea about how to modify bfs algorithm for finding the path containing specific nodes without back and forward edges? Can you write a pseudocode example?


texts: Perfect matching in a graph and complete matching in bipartite graph

texts:
When I google for complete matching, first link points to perfect matching on wolfram.

It defines perfect matching as follows:

  A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching.  A perfect matching is therefore a matching containing $n/2$ edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices.

However below graph contains even number of vertices (10 vertices), but still I cant guess the perfect matching - in which every vertex of of the graph is incident to exactly one edge. One of the matching can be $\{E_1,E_4,E_6\}$. However not every vertex (here, $\{V_5,V_6,V_9,V_{10}\}$) is incident to exactly one edge in this matching as required by above definition. So this is not definitely a perfect matching as desired by wolfram's definition. Also I cannot add any other edge to this matching as it will make two edges to share a vertex.

Q1. Is perfect matching possible with this graph?

I am also reading the same topic from the book by Narsingh Deo. It defines the complete matching in the context of bipartite graph:

  In a bipartite graph having a vertex partition $V_1$ and $V_2$ a complete matching of vertices in set $V_1$ into those in $V_2$ is a matching in which there is one edge incident with every vertex in $V_1$. In other words, every vertex in $V_1$ is matched against some vertex in $V_2$.

I am not able to understand if these two (wolfram's and book's) definitions point to two different concepts or they are one and same.

By my understanding, according to Deo's definition, $V_2$ may contain more vertices than that in $V_1$, thus the size matching may be less than $n/2$. However, wolfram says perfect matching contains $n/2$ edges. For example in above graph the complete matching of vertices in set $P_1$ into those in $P_2$ can be $\{E_1,E_4,E_6\}$ as one edge in this matching is incident with every vertex in $P_1$.

Q2. So the two definitions (wolfram's and book's) must be different concepts. Am I correct?


texts: Proof that languages are Turing-recognizable iff computably-enumerable

texts:
A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.
In the "only if" direction, we assume that a Turing machine $M$ recognizes some language $L$. We list all the strings in the input alphabet (in lexicographic order, say) as $s_1,s_2,s_3,\dots$
We then construct an enumerator $E$ that for each $i=1,2,3,\dots$ simply runs $M$ for $i$ steps on each input $s_1,s_2,s_3,\dots, s_i$; then it prints any $s_j$ which is accepted by $M$. $E$ is what we need.
Now, since I know that strings are finite, why should I run $M$ for $i$ steps on the first $i$ strings, when I could just run it on the $i$-th string? It feels like an unnecessary complication.
P.S. Another question was asked about this, but it addressed a different doubt:
Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."


texts: MIPS Architecture : PC-relative addressing

texts:
In case of branch Instructions such as beq, bne, we use PC-relative addressing.
But I am really not clear why it is said in most of the books that MIPS address(while calculating branch target) is actually relative to the address of following instruction PC+4 as opposed to the current instruction PC?

Anybody please explain me.
Thanks.


texts: In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\vee y\vee y)$ work instead? Isn't the truth table identical?


texts: Among $k$ unit vectors, find odd set with sum length less than 1

texts:
I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no such set exists?

As some motivation, if I have 3 vectors (so that $n=1$), the minimum value of their pairwise dot products if $-3/2$, given by them forming the corners of a triangle. This places all 3 vectors in the same two-dimensional plane. Anything out of that plane (so, more than 2 dimensions) will raise the minimum to some sum $>-3/2$. If I go to a fewer number of dimensions by constraining all the vectors to 1D, then my only possible sums are -1 or 3.

In general, if I have $2n+1$ vectors, then by putting them at corners of a $2n$-simplex, you get a sum of dot products of $-(2n+1)/2$. But by putting them in 1D, you get a minimum of $-n$. I'd like to find sets of vectors that "don't look very 1D" in the sense that they violate this bound.

This is equivalent to the question, "Find an odd-size set of vectors such that their sum has length less than 1" -- the equivalence can be shown by taking the norm of the sum. I think this is more natural, so I'll change the question title.


texts:
Let $A$ be a problem. I would like to solve $A$ in $NL$. So, I am trying to construct Turing machine working in $NL$:

Let $w$ be a input of length $n$. Firstly, we run machine $M_1$ that working in $LOGSPACE$. It produces a output $o$ of length $P(n)$ where $P$ is a polynomial.
Secondly, a machine $M_2$ working in $NL$ reads the output $o$ written by $M_1$.

Does t work in $NL$? Why?

P.S. If machine $M_2$ worked in $L$ it would be obvious that problem is solvable in $L$. But, I am not sure if that algorithm solves $A$ in $NL$.


texts: Why does the proposer sends an accept request with the same value it got from the acceptor?

texts: In the second phase of the paxos algorithm, the proposer issues an accept request with the number n and the value v it got from the acceptor, if the acceptor has already chosen a value previously. My questions is why the proposer is doing this? Because once a value if chosen it is permanent and cannot be changed, so in this case the proposer is just learning the chosen value, which was sent in the response of the prepare request. Why would it asks to accept a value already accepted?


texts: Proving that a spanning tree of graph is not a minimum

texts:
Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$.

Now I assume that there exists a spanning tree of $G$, let's call it $T'$, that has a path from node $u$ to node $v$ with all edges in a path from weight $<w_i$ for some $1 \le i \le n-1$. And I assume that the path from $u$ to $v$ in $T$ has at least one edge with weight $\ge w_i$. I other words, the path from $u$ to $v$ in $T$ has an edge which is heavier than all the edges in the corresponding path in $T'$.

I need to prove formally that $T$ is not a MST.

What I've tried is to somehow find a tree which is of less wight than $T$ using Kruskal's algorithm, but I couldn't manage to do it.


texts: Real world example of contraction and weakening

texts: Can you provide me a real world example of contraction and weakening in the type system of a popular language like Java, Kotlin, etc.? I heard that Rust has got explicit contraction but I don´t understand how this influences how we use such a language.


texts: Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)?

texts:
According to wikipedia, Cocktail-sort has an average performance of $O(n^2)$, whereas Comb-sort's average performance is $Ω(n^2/2^p)$, where $p$ is the number of increments.

There's no explanation given for this substantial difference between two similar algorithms, both variants of Bubble-sort. Can anyone help explain it?


texts: How to represent sentences with their dependency parses as input to an RNN?

texts:
I am working on a task embedding sentences into a lower-dimensional space according to style, both grammatical and lexical.  As such, I want to have as input the linear ordering of tokens in each sentence, together with its dependency parse as provided by spacy.

In particular, I'd like to find a way to tie together the representation of the linear order of tokens and the representation of the dependency parse, so the network could learn features like "this sentence used a word with an embedding close to Y as an nmod which came before and modified a word with an embedding close to Z".  How could I design such a network?

Edit: The desired input to the network is a parsed sentence; the desired output is a vector which allows that sentence to be compared with others in terms of both lexical and syntactic features.  I know how to use an RNN with a sequence of word-vector embeddings as input.  I also know how to encode a tree of grammatical functions as a sequence of tokens starting from the root.  I'm not sure how to create a unified representation of the sentence where I can determine, for instance, both the embedding and the grammatical function of the fourth word in the sentence and the embedding of the word it modifies (requiring knowledge of the edges between words as well as their linear ordering).


texts: Smallest convex set containing given point

texts: Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is there an (efficient) algorithm that finds $n+1$-subset of $M$ with smallest convex hull that contains $x$ (or, $k$-subset for some $k < n + 1$ if such exists)? "Smallest" is defined according to the volume in $R^n$ (or $R^{k-1}$). "Efficient" would imply something much better than the brute force strategy that examines all $n+1$-subsets of $M$.


texts:
There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix).

As far as I have understood,that is because we have to ckeck all the nodes per every node, that is, when checking the first node's best edge, we have to check edges from the current node to all other nodes. That makes $(n-1)$ edges at most. We check this for all nodes, so it would be n*(n-1) edges to check at most.

So why is the time complexity $O(n^2)$?

In addition, why don't we consider the edges which create a loop and why don't we ommit them in the algorithm? Does that make any difference in the time complexity?


texts: How can the union of two 'context-free but not regular' languages be regular?

texts:
I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:

  If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined over the same alphabet $Σ$ then, the union $L_1∪L_2$ can be a regular language.

I can't find an example to prove that this statement is true because by definition the context-free languages are closed under union operation.

Could someone please provide an example?


texts:
We're given these two finite state machines where the alphabet consists of ${a, b, c}$. The question is to determine the language for the following two machines. I tried following the machines to find the language, but the languages I derived are quite verbose.

FSA #1

This FSA accepts words with at least one a followed by zero or more b's or words with at least one a followed by zero or more b's followed by at least one c.

FSA #2

This  FSA accepts words with at least one a followed by at least one b or words with at least one a followed by at least one b followed by one c.

I tried converting these FSAs to regular expressions and found that my solutions hold up, but I'm wondering if there is a more concise way to explain the language of each FSA. My language explanations seem quite verbose, so any help would be appreciated.


texts: What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

texts:
If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"

This strikes me of being a relative of the Halting Problem, but I just don't know the taxonomy here.

What is the name of this problem, or does it not have a name because it is solved/uninteresting?


texts: How to tell if a language is recognizable, co-recognizable or decidable?

texts:
If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?

Basically any hints or tricks that can be used to tell. Or maybe the common patterns to search for to tell which kind it is?


texts: Can parameters other than $n$ be always ignored in big $O$ notation?

texts: The Bentley–Ottmann algorithm, for example, has time complexity of $O((n + k) \log n)$. Is the statement $O((n + k) \log n) = O(n \log n)$ true? I know that $k$ is there because it has big enough of an impact on the overall time complexity that it's relevant to include it. But can it be ignored, so that the previously stated equivalence holds, and hence we can without any reservations say that the algorithm has time complexity of $O(n \log n)$?


texts: How do i tell if a network is not sorting network?

texts: For most sorting network diagrams how do you work out that it is not a sorting network? What is the method to work it out ?


texts: Use of Big-O Notation: Size of Input vs Input

texts:
It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size of the input as opposed to the input itself (particularly in the case of numeric algorithms).

For instance, trial division for integer factorization takes up to $\sqrt N$ divisions to factor the integer $N$.  However, the size of the input is the number of bits, $w = \lg(N)$.  Thus, integer factorization takes $\mathcal{O}\left(2^{w/2}\right)$ time with respect to the size of the input ($w$ bits).

My question: Given the above, would it be considered correct to write in a CS article  (relatively informal--on the scale of a blog post) to write that "integer factorization takes $\mathcal{O}(\sqrt{N})$ time with respect to the input variable $N$," and assume that the reader realizes they should substitute $w=\lg(N)$ to obtain the time complexity with respect to the size of the input?


texts:
Suppose the readers writers problem had a third process where they can both read and write. So we have readers that can only read, writers that can only write, and rw that can both read and write. What would a petri net look like that modelled this?
Does anyone know of a source that would show this?


texts: efficient algorithm for min cut with specified number of vertices

texts: Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to minimize the number of edges going between $C$ and $\bar{C}$. Algorithms are known for this problem which solve it in polynomial time. My question is, what if one additionally specifies the constraint that $|C| = n$ for some $n < |V|$? That is, we wish to find the set of $n$ vertices with the minimal number of edges connecting it to the rest of the vertices. Are there also efficient algorithms for this case? I am interested both in the question of whether this problem is formally solvable in polynomial time (which I would guess that it is) and also in what algorithms are best in practice.


texts: approaching dynamic programing for problem

texts:
I want to find a solution to a problem that asked before.
in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-edgest

I have a directed graph with colored edges (red & blue) that may contain cycles. The question is to write an algorithm given two vertices (s,t) that finds the path with the minimal number of color changes between s and t (if such path exists).
$

suggesting a reduction to solve the problem.
I want to find an optimal structure for the problem by:
$opt(v) = \min_{u \in In(v)}(opt(u) + f(u,v))$
$f(u,v)$ define:
$f(u,v) = \begin{cases}  1, & \text{the color of (u,v) same as the color that appears more}, \\
-1, & \text{the color of (u,v) the color different from the color that appears more}.\\
1, & \text{else}
\end{cases}
$
the problem with that formula is that the optimum of the neighbors, not gratitude the optimum solution for  $v$ because considering v that have 1 neighbor with a blue edge that has a path with the same blue and red edges and another path with 1 more red edge than my structure return 1 however there is a path with 0 alterations.
then I thinking to save for all the vertices 3 paths, optimum path most optimum path with more blue and path with more red but its seem to complicated to build a formula with that filed.


texts: Planar graphs of bounded degree: mixing time = cover time?

texts: For many planar graphs of bounded degree (binary tree, lattice, cycle) the (1/4)-mixing time and the cover time are equal, up to log-factors. Is this always the case?


texts:
Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the experiment.

I would like to allocate users to each experiment, at the point where a user might be exposed to the logic for that experiment. I would like to assign users to experiments such that experiments implemented downstream (on pages that are usually seen last) still get users assigned to them.

For example, if user A is runs into the code logic for experiment A at login and then goes to page B and runs into experiment B, the user A could be assigned to either experiment A or B. That means that they will only see one of the experiments and not both (either A or B) or neither. I would like to figure out the right algorithm so that experiment B (which is downstream and shown to the user after they've seen experiment A) gets users assigned to it. I don't to assign all users to experiment A.

So the flow is as follow

User visits page A where experiment A is implemented
We decide whether to assign users to experiment A. If user is assigned to A, user will be able to see experiment A.
User visits page B where experiment B is implemented, we decide whether to assign users to experiment B
Users can only see experiments that they are assigned to.
I want to come up with an algorithm that allows me to assign users to
experiments regardless of where on the site they are implemented so that the traffic distribution is efficient and experiments implemented downstream get enough users.

Can someone please point me in the right direction to an algorithm that allows me to do the above?

Each experiment is given X number of people needed per day to reach stats sig. We could factor that into the algorithm to make sure that we assign users to experiments in a way that experiments reach their sample size in two weeks.

A possible algorithm:

For each experiment, we make a decision of whether to assign based on the experiment's location using coin flip.
If we get heads, a list of experiments that are implemented for that location are selected.
An experiment is chosen from that list based on priority system.
At every location, a % of users are assigned to one of the experiments implemented at that location.
When we decide to assign or not to assign to any experiments at that location, that decision is not made again for the user.

The Question:
How do I assign users to one experiment at a time so that experiments that they might see last get enough users? Only users assigned to experiments can see them.


texts: Efficient computation of traces of all primitive elements in field extensions of GF(2)

texts:
Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from $\mathbb{F}_{2^n}$ to $\mathbb{F}_2$. There are $\phi(2^n-1)$ primitive elements in $\mathbb{F}_{2^n}$ (generators of the cyclic multiplicative subgroup of the field) where $\phi$ is  Euler's totient function.

I am interested in computing the traces of all the primitive elements in $\mathbb{F}_{2^n}$ efficiently. Note that all the primitive elements are given by $\alpha^k$ where $\alpha$ is one of the primitive elements, and $\gcd(k, 2^n-1) = 1$. Moreover two primitive elements $\alpha^k$, $\alpha^s$ have the same trace if and only if $k \equiv s\cdot 2^i \pmod{2^n-1}$ for some $i$ with $0 \leq i \leq n-1$. This means we need to compute $\phi(2^n-1)/n$ traces.

Is there an efficient algorithm to do this?


texts: In a binary system we know that the next floating point number after 4 is 4+1/32. What is the machine epsilon? Is it 1/32 and if yes, why?


texts:
$L=\{w \mid w \in \{a,b\}^*$, $\text{the number of a's is at least the number of b's} \}$

I'm stuck trying to build an NPDA that accepts $L$.


texts: Sets whose decimal expansions form a regular language

texts:
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \mid n \in S\}$. Is there a nice characterization of the sets $S$ such that $\bar S$ is a regular language?

Obviously adding or removing a finite number of values doesn't affect the regularity of $\bar S$, so what matters is only the “asymptotic” behavior of $S$, i.e. what it looks like above a certain threshold.

For numbers written in unary, there's a simple characterization: the corresponding set of representations is regular iff the set is ultimately periodic (i.e. it's of the form $\{a n + b \mid n \in \mathbb{N}, b \in F\}$ for some finite set $F$ and some constant $a$). An ultimately periodic set's set of expansions is a regular language: it's a finite union of images of affine functions, which are regular. There are other sets whose set of expansions is regular, such as $\{10^n \mid n \in \mathbb{N}\}$. On the other hand, the set of squares doesn't have a regular set of expansions.

In general, how can $S$ look like when $\bar S$ is regular? Is there a simple arithmetic characterization of sets whose sets of expansions is regular?


texts: Is type-checking "syntactic" or "semantic"?

texts:
On the wikipedia page on compilers, it says:

  Semantic analysis adds semantic information to the parse tree and builds the symbol table. This phase performs semantic checks such as type checking (checking for type errors), or object binding (associating variable and function references with their definitions), or definite assignment (requiring all local variables to be initialized before use), rejecting incorrect programs or issuing warnings. Semantic analysis usually requires a complete parse tree, meaning that this phase logically follows the parsing phase, and logically precedes the code generation phase, though it is often possible to fold multiple phases into one pass over the code in a compiler implementation.

I was somewhat surprised that type checking is categorized as semantics rather than syntax. Usually my impression is that types are called syntactic objects. Is type checking syntactic or semantic?


texts: What data structure would help find nearby coordinates quickly?

texts:
I need to write a program that does the following:

Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places
Store them in a data structure once
Provide a "nearby" lookup function that can efficiently return the N closest objects for a given lat/long

Currently, I'm doing the following, which is suboptimal:

Store all objects in a hash, with array keys like [integer_latitude, integer_longitude]
At search time, find all objects in an arbitrary-sized circle around the target. Eg, if the search is at [0,0], I can get all objects within 1 degree by pulling [-1,0], then [0,0], then [1,0], then [0,-1], etc.
Order the found objects by actual distance to the target and take the top N

This is obviously inefficient, because often there are many more matches than N.

One improvement could be to examine locations in concentric squares outward from the center: all points 0 degrees from the center, all points 1 degree from the center, 2 degrees, etc, and stop after the first square when I have at least the number of objects needed. Then I could sort those by actual, fine-grained distance and take the top N.

Is there some well-established way of doing this search efficiently?


texts: Efficient algorithm for assigning weights to nodes in graph to create steady state flow

texts:
I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem:

Definitions:
Given a graph $(V,E)$, with non-negative weights assigned to it's edges $w_E:E \rightarrow \mathbb{R}^+\cup\{0\}$ and non-negative weights assigned to it's vertices $w_V:V \rightarrow \mathbb{R}^+\cup\{0\}$ we define the flow on the edge $e=(v_1,v_2)\in E$ to be the wight of the vertex where the edge starts times the weight of the edge, $f(e=(v_1,v_2)) \equiv w_V(v_1)\cdot w_E(e)$. The inward flow to vertex $v\in V$ is defined by the sum of the flows on all inward edges $f_{in}(v) = \sum_{e\in E\;s.t.\; e=(u,v)}f(e)$ and the outward flow the sum of flows on all the outward edges $f_{out}(v) = \sum_{e\in E\;s.t.\; e=(v,u)}f(e)$.

The Problem
Given a finite directed graph $(V,E)$ and an edge weights assignment $w_E$, find a non-trivial weights assignment to the vertices $w_V$ such that the inward flow and the outward flow are equal for each vertex, $\forall v\in V\; f_{in}(v) = f_{out}(v)$. The trivial solution is $w_V\equiv 0$. Notice that I'm only looking for one non-trivial solution (there could be more than one). If there is no non-trivial solution the algorithm should return some error message.

Any ideas?
Thank you for your help


texts: Why does the state remain unchanged in the small-step operational semantics of a while loop?

texts:
Usually I see that in the structural operational semantics representation for the while loop, the program state don't change:

$(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma)$

For me, this not intuitive, if the state don't change (i.e. the status of the memory stays the same) then $B$ will continue to stay true and the program will never terminate.

Can anyone please explain why the state don't change in this rule?


texts:
I know that  languages which can be defined using regular expressions and those recognisable by DFA/NFA ( finite automata ) are equivalent. Also no DFA exists for the language $\{0^n1^n|n \ge 0\}$. But  still it can be written using regular expressions ( for that matter any non-regular language can be ) as $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$ . But we know that every language that has a regular expression has a DFA that recognises it ( contradiction to my earlier statement ).
I know this is a trivial thing, but does the definition of regular expression includes the condition that it should be finite ?


texts:
$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$.
  $L_1$ is reducible to $L_2$ in polynomial time. Which of the following
  cannot be true?

  $L_1 \in P$ and $L_2$ is finite
  $L_1 \in NP$ and $L_2 \in P$
  $L_1$ is undecidable and $L_2$ is decidable
  $L_1$ is recursively enumerable and $L_2$ is recursive

My reasoning is as follow,

If $A \le_p B$, and $B \in P$, then $A$ can be reduced to $B$ in polynomial time and solved in polynomial time making $A \in P$. Thus I initially figured the 2nd choice as false and thus the right answer.

However using the same argument on mapping reducibility, the 3rd choice seems to be false as well. The fourth choice is the same as the third one.

I was unsuccessful in reasoning anything about the 1st choice.

To put my above arguments in context, I am learning about theory of computation and have just about skimmed the surface of computability and complexity theory. Helo me out.


texts: Is my theorem about $P \neq NP$ correct?

texts:
It is known that there are problems in P that, provably, are not
solvable in less than $O(N^k)$, for some $k$. Now consider some infinite
set $K \subseteq \mathbb{R}^+_0$ such as K is unbounded from above (you
can think of $K$ as being $\mathbb{N}$, for easy reasoning).

Theorem: If there exists at least one problem in P for each $k \in K$ that can't be solved in less than $O(N^k)$ steps, then $P \neq NP$.

Proof: Assume that $P = NP$, what implies that there is an algorithm that can solve some NP-complete problem in $O(N^q)$ steps, for some $q$. Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$. Thus, every problem in $NP$ (so, also in $P$) can be solved in $O(N^r + N^q)$ steps. Since $K$ is unbounded from above, there are infinitely many $k \in K$ such as $O(N^k) > O(N^r + N^q)$, and so, for each of these $k$, there is at least one problem in P that can't be solved in $O(N^r + N^q)$ steps. But, since we assumed $P = NP$, every problem can be solved in $O(N^r + N^q)$. Contradiction!

So, to prove that $P \neq NP$, it suffices to find a class of
hard P problems, parameterized by a number $k$ -- lets call each of them
HARDP-$k$ -- that for each given $k$, it is proven that the best
algorithm that solves HARDP-$k$ has time complexity of $O(N^k)$.

If such a class is too hard to define, other less straight
strategies can be taken. For instance, without actually defining
HARDP-$k$, it suffices to prove that there exists infinitely many
problems in P with ever increasing time complexity for the best possible
algorithm that solves it.

So, my questions: 1) Is my theorem correct? 2) Is it already known? 3) Is it of any relevance?


texts: Is this possible to solve 3SAT in O(n^24) time and O(1) space?

texts:
Assume that n is the number variables of the given 3CNF formula (n≥3) and all clauses in the given 3CNF formula are different.

That means that for each clause, each literal can be either positive or negative and be one of the n variables, so the number of options for each literal is 2n, but each clause has exactly 3 literals, so the maximum number of different clauses is 2n•2n•2n = (2n)3 = 8n3 = O(n3).

I have read here that 3CNF formula must have at least 8 different clauses in the form:

(x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)

to be unsatisfiable.

If this small 3CNF formula is included or subset of a larger 3CNF formula, then the larger 3CNF formula is unsatisfiable for sure, because of that subset.

So the algorithm needs to search for this subset and if the algorithm found it then the algorithm returns "given formula is unsatisfiable" as output.

And this suppose to be correct for sure.

But what happens if the algorithm doesn't find such subset?

Does this necessarily means that the given 3CNF formula is not unsatisfiable, i.e. satisfiable?

Because that the subset has exactly 8 clauses, the algorithm needs to iterate through all the different subsets of 8 clauses in the given 3CNF formula.

If the given 3CNF formula has m clauses, then there should be θ(m8) different subsets of 8 clauses, but if all clauses are different, then m=O(n3), thus O((n3)8) = O(n3•8) = O(n24)

So the running time of the algorithm to iterate through all these subsets and to find the unsatisfiable subset, if exists, takes θ(n24) time.

To do this, the algorithm needs 8 inner for loops, where each for loop is inside the other, with 8 iterative variables.

Because that the algorithm doesn't allocate any memory during the run time, the space complexity of this algorithm suppose to be θ(1).

Let me know if I was wrong and on what, i.e. if I am wrong then why?

Why I was wrong?

Please explain.

I want to learn from mistakes.

I think that

it's too good to be true

and

if it's too good to be true, something's wrong.


texts: Scopes vs objects -- would a language make sense that voids the difference?

texts:
So there's this adage that says "Objects are a poor man's closures", which can equally well be reversed, which I understand to mean that they are equivalently expressive.

What strikes me about the semantics of JavaScript, is that this adage seems to come way closer to home, due to these two facts:

Function execution frames are scopes that essentially reside on the heap (depending on the implementation is of course), because they're closures. Without something like escape analysis you cannot throw the scope away after the function ends executing. I.e. the classical distinction stack/heap is no more.
But more importantly, JavaScript's prototypal inheritance works the same way as lexical variable lookup.

The only "real" difference between scopes and objects in JavaScript seems to be that whereas you can programmatically make new objects with a given prototype, you cannot programmatically make a new scope with a given lexical parent.

My question then:

Would it make sense to void the distinction altogether?
Have people seriously considered this before, maybe discarded the idea due to some really obvious problems?

To be clear, I'd be talking about a language like this:

// (1) A scope is like an "object builder", and it's lexical
//     surrounding is like the object prototype chain

let adjective = "awesome";
let o = { let name = "objects"; let adjective = "boring" };
let s = { let name = "scopes" };
let describe = concept => `${concept.name} are ${concept.adjective}`
console.log( [o, s].map(describe) )
// ["objects are boring", "scopes are awesome"]

// (2) An example of what inheritance would probably look like

let Animal = numLegs => { let canSpeak = false }
let cat = Animal(4)
// cat.canSpeak == false, cat.numLegs == 2

let Person = name => { extend Animal(2); canSpeak = true }
let kelley = Person("Kelley")
// kelley.canSpeak == true, kelley.numLegs == 2, kelley.name = "Kelley"
```


texts: Streaming algorithm for counting triangles in a graph

texts:
As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it can easily be shown" that
$$
E[\hat T] = T
$$
But unfortunately, I'm not seeing it. Trying to analyze $E[\hat T]$, I think as follows:

At line 1, denote the probability to randomly (and uniformly) choose an edge which is part of a triangle as $p$. Since triangles can share edges,
$$
   \frac T m \le p \le \frac {3T} m
   $$
For example, consider the following case:

The central triangle doesn't add new edges to the # of possibilities to choose an edge which is part of a triangle. You can imagine a different configuration, in which there are only the 3 outer triangles and they don't touch each other (in this configuration, we won't see the central 4th triangle). In both cases ((case i) 4 triangles as seen in the image; (case ii) 3 disjoint triangles), the probability to choose an edge which is part of a triangle is 1 (although the # of triangles is different).

At line 2, the probability to choose uniformly at random a vertex which "closes a triangle" with the edge from the previous step is exactly $\frac 1 {n-2}$.

Therefore I only see that
$$
T \le E[\hat T] \le 3T
$$
What am I missing?

Another question I have is regarding line 3. The stream is ordered, and we first pick a random edge $(u, v)$ (line 1), then a random vertex $w$ from $V \backslash \{u, v\}$ (line 2). I feel that the analysis should take into account that at line 3 we check whether $(u, w)$ and $(v, w)$ appear after $(u, v)$ in the stream. Maybe after I'll understand the answer to my first question, it will be clearer.

Algorithm:

Pick an edge $(u, v)$ uniformly at random from the stream.
Pick a vertex $w$ uniformly at random from $V \backslash \{u, v\}$
If $(u, w)$ and $(v, w)$ appear after $(u, v)$ in the stream, then output $m(n-2)$. Else, output $0$.

Also, although I didn't see it written, I believe there's an assumption that $V$ is known ahead.

Reference: Data streams lecture notes by Prof. Amit Chakrabarti, section "15.3 Triangle Counting", https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf

Best regards


texts: Looking for prior occurrences of $k$-CNF efficiently translated to coloring?

texts:
Has anyone else ever translated 3-cnf (4-cnf) on $N$ variables and $M$ clauses
into 4 coloring on $O(M)$ vertices?  By taking two variables from a clause,
the four boolean combinations correspond to four colors. The two
halves of a clause correspond to two vertices, and the clause itself
is a color constraint between the two vertices.  Of course, the
third variable of each clause must be well handled as a vertex.
Graphs are complex boolean circuitry, and a 4 coloring defines
a satisfying assignment on the $N$ variables.
I am looking for any previous occurrence of this compact translation of
$k$-sat on $N$ variables and $M$ clauses into 2^$(k/2)$ coloring on $O(M)$ vertices.
Usually, coloring is translated to sat for solving, but, I am translating
sat efficiently to coloring for solving.
When I do so in my solver, bob, the solution procedure is very interesting,
becoming simple graph coloring, with just depth first search.  An inference
reduces to one dozen cpu instructions.  Think of "ergo" below as a unit
propagation system, where long coloring cascades occur as vertices are
reduced to one possible color.
num yaystonays(num z) // turn color z off in a vertex.
{ when(t_r_e_e & ones[z]) {
    t_r_e_e &= diagovreason[z];
    count = countdown[count];
    env::zeesva[env::zeesvg++] = usiv + z;
    when(one == count) return ergo(); }
  return count; }
num ergo() // vertex has just gone down to one color
{ nums& m = *oneways.v[unity(t_r_e_e, wyde())];
 for num g = zero; g < m.y; g++) // assert all remaining memory
  { num y = m.v[g];
    when((*env::allBobs.v[y >> siv]).yaystonays(y & tau[siv])) continue;
    return (*env::allBobs.v[zero]).yaystonays(zero); }
 return one; }

The bulk of the inferencing becomes simple assertions of coloring, and the
number of LIPS (Logical inferences per second) goes well over 500 million on 5GHz. .
Resolution and subsumption become unnecessary for solving sat.  With higher
$k$-cnf, the number of boolean variables per vertex is $k/2$, with 2^$(k/2)$
possible colors.  Larger cases are still exponential.  Moderate sized
cases are polynomial.
I am trying to enter bob into the 2021 model counting competition.
Source for bob is available by email.


texts:
Density-reachability is a canonical extension of direct density-reachability.
What is meant by canonical extension?

Source: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf


texts:
I'm doing this course: Engineering: Algorithms1 - SELF PACED Algorithms: Design and Analysis, on Stanford's website. And the first assignment asked us to count the inversions in an array.

The idea that they used was:

Break the original array in half.
Count the inversions in each half
Pass the original array through mergeSort to get the split inversions

If this is so, then I do not understand how can the mergeSort not recount the inversions from each half.

From what I thought, every time I pick the element from the right array over the element from the left array that would be an inversion. And since we work recursively into basic single elements of the array, this would also go through each of the halves when merging, therefore recounting.

Am I missing something?


texts:
I would like to know if my understanding of this is correct:

The question asks to show that the Big-Oh of the following function is $O(n\log(n))$

$$
\log(n^n + n)
$$

I think the first step is to play with the expression so:

$$
\log(n^n + n) = \log(n(n^{n-1}+1)) = \log(n) + \log(n^{n-1}+1)
$$
However, I don't know what to do next.
Please help me move forward.
Thanks.


texts: Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?

texts:
I am reading http://okmij.org/ftp/gengo/applicative-symantics/AACG1.pdf and there is defined language TL (see last row in the table on page 4). It seems to me from this definition of TL, that lambda calculus is the language of universal logic - each connective (unary, binary, ternary, etc.; quantifiers can be expressed in this language as well - as unary functions) is just another function (of type t->t->t - for binary connective) and the only difference between this simple function and connective function is the following: connective functions have constraints in the form of logical rules (e.g. connective or quantifier introduction or elimination rules), simple functions have no such rules.

So - my questions are:

Do I understand correctly, that lambda calculus is (can be) the language of Universal Logic (in the tradition of https://link.springer.com/journal/11787)? If no, then why not? If yes, then why there is no wide adoption of lambda calculus in the Univeral Logic community?
Do I understand correctly that connectives are just another functions with the constraints. Is it possible to defined constraints on other functions (simple functions) in the lambda calculus without changing the base logic? I.s. how logical rules for connective functions differ from the user-defined additional rules/constraints for simple functions?

So - the fully hierarchy of the logics can be defined purely by the introduction of connective functions in lambda calculus and by the additional rules on them. So simple?

Of course, I am aware of Curry-Howard isomorphism but its talk about "propositions as types, proofs as lambda terms" is somehow disconnected with the straight appearance of lambda calculus as the language of universal logic. Maybe there exists answer that connects my feelings about lambda calculus as the language of universal logic with the CHI.


texts: Minimal number of changes to make string into concatenation of $k$ palindromes

texts:
The following question is taken from leetcode: 1278. Palindrome Partitioning III

  You are given a string $s$ containing lowercase letters and an integer $k$. You need to:

  First, change some characters of $s$ to other lowercase English letters.
  Then, divide $s$ into $k$ non-empty disjoint substrings such that each substring is a palindrome.

  Return the minimal number of characters that you need to change to divide the string.

So I did find the cost array to make a string to a palindrome. Something like below:

[('bcccdefg', 4), ('ccde', 2), ('ccdef', 2), ('ef', 1)] # (character, cost to make it a palindrome)

I am thinking whether this can be done using knapsack recurrence relations, where profit will be cost and weight will be length of the substring; the total backpack weight will be the length of the main string. Though I am not sure what to do with $k$. Do I need 3 states, or are 2 states enough?

Is my thinking correct? If no, what is the right way to write a recurrence relation for this?


texts: Represent there are infinitely many in FOL

texts:
How to represent in first order logic the expression:

  "there are infinitely many"

To be honest I'm confused and not even sure whether you can represent them in first order logic.


texts: Moving an edge in a weighted tree to maximize longest path length

texts:
Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$, where $x,y \in V(G)$. Intuitively, we can think of the move meaning the deletion of an edge, and the re-insertion of it between two new vertices.

Now, given $G$, our task is to maximize the weight of a longest path in $G$ by a single move with the constraint that the newly obtained graph $G'$ remains a tree. An example is given below:

The longest path is E-B-C-D with weight 18 at the initial state. But if we move B-C to E-F we get a longest path A-B-E-F-C-D with weight 23.

One could rely on brute force, which is a feasible approach: remove an edge, try putting it between two vertices, check if a graph is still acyclic, find the longest path, try another pair of vertices, try another edge. You will end up with enumerating all possible acyclic graphs.

My question is the following: could we do better than brute-forcing all possibilities?


texts: Why is automatically labeling data in unsupervised learning hard?

texts:
I currently studying machine learning and pattern recognition area. Today, my professor said implementing an unsupervised system that automatically labels data is difficult. Why is that?

I think if I am given a data set, then I can categorize all data into groups. Then, for unknown input data, I can extract features and put it into the group that best fits all the features. Can anyone explain whats wrong with my intuition and why is it difficult problem?


texts: How to understand the solution to Task Scheduler problem on LeetCode?

texts:
LeetCode Task Scheduler problem is the following:

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There are at least 2 units of time between any two same tasks.

Example 2:
Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

This is a solution I found:
    def leastInterval(self, tasks: List[str], l: int) -> int:
      freq = [0]*26
      maxOccurrence = 0

      for task in tasks:
        freq[ord(task) - ord('A')] +=1

      freq.sort(reverse=True)

      idleBlocks = freq[0] - 1
      idlesState = idleBlocks * n

      for i in range(1, 26):
        idlesState -= min(freq[i], idleBlocks)

      return len(tasks) + max(0, idlesState)

Basically, it works like this:
Given the tasks  ["A","A","A","A","A","A","B","C","D","E","F","G"]

Sort the tasks by frequency descendingly

{ A: 6, B: 1, C: 1, D: 1, E: 1, F: 1, G: 1 }

We first place the most frequent character. All the spots between the same characters are first idle.

A _ _ A _ _ A _ _ A _ _ A _ _ A

We try to fill the remaining characters in the idleSpots using the sorted task array. (most frequent filled first)

A B C A D E A F G A _ _ A _ _ A

If the idleSpots < 0, we return the total number of tasks, else we return the total number of tasks + idleSpots.

I'm having issues proving this statement:
If the idleSpots < 0, we return the total number of tasks.
In other words, if we manage to fill all the idle spots between the most frequent character, why are we sure to complete all the tasks without complimentary idle tasks?
How come we can't we end up with a case like this
A X X A X X A B _ _ B _ _?
Where X represents a character such that the idle spots between all the As are filled.
Can you give me some hints?


texts:
I am a bit confused on the difference between Cyclic Redundancy Check and Hamming Code. Both add a check value attached based on the some arithmetic operation of the bits in the message being transmitted. For Hamming, it can be either odd or even parity bits added at the end of a message and for CRC, it's the remainder of a polynomial division of their contents.

However, CRC and Hamming are referred to as fundamentally different ideas. Can someone please elaborate on why this is?

Also why is the CRC compared with the FCS(Frame check sequence) to see if the received message is with or without error? Why not just use the FCS from the beginning? (I might be totally flawed in my understanding by asking this question, please correct me.)