texts: How do I find out what states this FSM has?

texts:
I have a homework assignment where I am supposed to make a visual representation of a deterministic FSM. Basically, the FSM is to accept the input string if it does not contain the letters a and c immediately after the other. The input alphabet I is I = {a, b, c}. As a hint, the class was told that 4 states would be enough and that three states would be endings. And here is where my problem lies: I have no idea how to know what states this machine is supposed to have.
This is what I have come up with so far:

States: A, B, C
Start: A
Input alphabet: {"a", "b", "c"}
Endings: ?

I have no idea how far this is correct or if there is something that I misunderstood about making FSM visual representations. Of course I don't want the solution, but rather hints or tips to point me in the right direction.

For clarification, here are a few accepted input strings as well as input strings that will not be accepted.

Accepted strings:

abbabcbabccb
cbaaabccbca
ab

Not accepted strings are:

abcbca
abbabcbabaccb

Please improve the question if possible (and add appropriate tags).

Edit:

This is my new attempt:


texts: In counting sort time complexity notation O(n+k), k is number of distinct elements?

texts:
Do I get right, that if we say that counting sort time complexity is O(n+k), this notation means that n is number of all elements to sort and k is number of distinct elements?

For example for array [ 3, 5, 7, 5, 1, 5]
n = 6 and
k = 4 ?


texts: What is the real reason that Bubble Sort runs at O(n) in best case?

texts:
In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only comparisons and no swaps in the inner loop.

But is that correct?  Are comparisons not counted in the complexity ? Only swaps?

Other sources claim the reason is only because it can be optimized with a ' flag' checking if it entered the inner loop.  In that case there would be ZERO swaps and n comparisons. ( If this reason is correct, can't I optimize other sorting algorithms this way? Likesay, selection sort?)

What is the correct reason?   I questioned both of the reasons!

EDIT: this is what is said in the link: "In the best case, it is of order n because it just compares the elements and doesn’t swap them"


texts: Why use minhash instead of directly computing Jaccard coefficient?

texts:
Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute.

But isn't it possible to also compute the Jaccard coefficient $\frac {|A \cap B|} {|A \cup B|} $ in $O(|A|+|B|)$ time by simply doing :

1  Given collections A' and B', create hash set datastructures A and B from them.
2. foreach(a in A){ if(a in B)sizeOfIntersection++; }
3. sizeOfUnion = A.size() + B.size() - sizeOfIntersection;
4. Jaccard = sizeOfIntersection / sizeOfUnion;

Assuming [an ammortized] O(1) hash set membership lookup, the complexity of the above is O(|A|+|B|), which is less than with k hash-function minhash.

So how is Minhash more efficient, and what benefit does it provide?


texts: What decision problems are their that are outside of elementary but still decidable

texts:
What decision problems are their that are outside of ELEMENTARY but still decidable?
I'm curious about problems that are still solveable, but take a very long time to do so.


texts: defining the operational semantics of a concurrent language

texts: As big-step operational semantics is about evaluating an expression to a final value, can we state that for defining a concurrent language one needs small-step semantics, as concurrent programs need not result in a value?


texts: Bipartite Graph to solve the wolf river crossing problem

texts:
I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving this question, now I was wondering how can we describe the problem in bipartite graph, as to describe it we need to divide the problem into two disjoint and independent sets, I am getting very confused as how it can be done?
It will be helpful, if someone can help me understand it as there is no information about this wolf river crossing problem on the internet.


texts: Algorithms with polynomial time complexity of higher order

texts:
I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting.

Linear Search - with time complexity $O(n)$
Matrix Addition - with time complexity $O(n^2)$
Matrix Multiplication - with time complexity  $O(n^3)$

Is there any algorithm with a higher complexity like $n^4$, $n^5$ etc? I would like to know about practical algorithms with polynomial time complexity only.

(I am familiar with algorithms having exponential complexity and class NP algorithms. My doubt is not about them.)


texts:
A) Solve this recurrence where $T(0)=0$ and write it in O-notation:
  $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$

So, I started to calculate:

  $T(1)=2(0)+c=c$

  $T(2)=1(0+c)+c=2c$

and so on, which gives me that $T(n)=nc$

This I can prove by induction: $(n-1) \rightarrow n$

  $T(n)= {2 \over n} (0+c+2c+...+(n-1)c)+c = {2 \over n} (c{(n-1)n \over
 2} )+c = nc$

Which gives me $O(n)$ (since $c$ is a constant). Am I right with this?

  B) For $T(n)=kT({n \over k})+ckn$
  find the closed form for the function $T(n)=f(c,k,n)$ (I don't know what does this mean) and write it in
  $\mathcal O$-notation.  If you had the algorithm working with $k=2$, $k=3$ or
  $k=4$ which one would you choose?

I'm stuck with this problem. With the help of the master theorem, I would get $log_k k = 1$ which would give $\mathcal O(n \log n)$ but how to find the closed form?


texts: Is SAT-Problem with XOR and AND NP-complete

texts:
Is this problem NP-complete?

I have many restrictions like this and want to find a feasible solution:

((a and b) xor (c and d)) = 1

with a,b,c,d are arbitrary literals. It looks similar to XOR-2SAT but has additional ANDs inside the clause.


texts: Can any PEG grammar be parsed in linear time?

texts:
On the Wikipedia for PEG it is claimed:

  Any PEG can be parsed in linear time by using a packrat parser, as described above.

However, packrat parsers can't handle left recursion.

You can eliminate any left recursion to create another grammar that recognizes the same language as the left-recursive one, however, those grammars are not equivalent because they do not result in the same derivation (e.g. a left-associative expr -> expr '+' expr becomes right-associative after left recursion elimination).

After doing some research I found a resource that can parse (indirect) left-recursive PEG, but it's not linear time.

So, is the claim on Wikipedia incorrect, or is there a linear time algorithm that can parse any PEG?


texts: term vs clause in the context of normal forms

texts:
In the context of disjunctive normal forms, which terminology do you use for the conjunction of atoms? E.g., for the disjunctive normal form $(x₁ ∧ ¬x₂ ∧ x₃) ∨ (¬x₁ ∧ x₂ ∧ x₃)$, how are the constituents "$x₁ ∧ ¬x₂ ∧ x₃$" and "$¬x₁ ∧ x₂ ∧ x₃$" called? Terms or clauses? I saw boths variants as well as "disjunctive clauses", and I wonder which variant is right.

There are lots of non-native English computer scientists around, so please reply only if you are an established computer scientist who actually taught this and have an excellent command of English.


texts:
I'm having trouble finding the language represented by the following:

(AA|BB)*

Should the expression be read as... ( A (A|B) B ) *
or... ( (AA) | (BB) )*

If that isn't clear, should this produce something like... ABABAB or should it produce AABBAABBBBAA

My guess is that AABBAA is part of the represented language, while AB is not.


texts: What is the appropriate algorithm for bipartite matching with constraints?

texts:
I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).

Let's say we have a lot of employees and a few jobs to be done. Each employee ranks the jobs they want most.

Easy. Bipartite matching, with weighted edges. Or Hungarian algorithm. Right?

Now things become more complicated. Instead of one job each day, an employee has to do 4 jobs in a day. The same single ranking they gave will be taken into account for the other 3 jobs they receive (no repetitions).

Since each employee must have 4 jobs, and there are many more employees than jobs, each job can have multiple people assigned to it for each period.

More complicated: each job has a maximum of employees it can accommodate (different for each job).

More complicated. Now jobs are skill based. Each employee has not only a preference ranking, but a skill class they belong to, low, med, or high. So each job has a phase for the low-skilled, the medium-skilled, and the high-skilled, with a skill level repeated for the fourth phase, as needed.

The objective is to make sure every employee ends up with the most of their highest ranked choices.

Does there exist some framework for solving such problems? Is there a way to adapt bipartite matching for all of these constraints?


texts:
Why is pure interpretation more common for scripting languages compared to programming languages?

I mean, why are programs written in a scripting language not converted to machine language and then executed? From what I have read, one of the reasons is speed; for scripting purposes speed is not so important and since interpretation is slower it doesn't matter for scripting languages.

Are there more reasons for using interpretation in scripting?


texts: How to define a language for an independent set problem of a graph?

texts:
Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\{u,v\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}_{>0}$ where $|I|=k$.

How can I define the language $L_{P_{Independent Set}}$ to this decision problem?

I know that $I$ could be written as $I = \{u,v\} \in V | \{(u,v)\}\notin E \}$ but don't really understand how to describe the language.


texts: Show that Knapsack-like problem on directed graph is NP-hard

texts:
Let $G=(V,A)$ represent a directed acyclic graph, where a value $v_i \ge 0$ is assigned to every vertex $u_i$. Let $T$ represent a threshold and $N = |V|$. Problem statement:

maximize: $\sum_{i=1}^{N}v_i x_i$

subject to: $\sum_{i=1}^{N} x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

and $x_i(x_j-1) = 0 \quad \forall a\in A: u_i \to u_j$

In other words, we want to choose up to $T$ vertices that maximize the sum of their values, with the restriction that if a vertex $u_i$ is chosen, any reachable vertices $u_j$ must also be chosen. Therefore, $x_i(x_j-1) = 0$ for a given arc $u_i \to u_j$ represents that if $u_i$ is chosen ($x_i = 1$) then $u_j$ must be chosen as well ($x_j = 1$).

I want to prove that this is a NP-hard problem. To do that, I have taken the 0-1 knapsack problem, which is NP-hard:

maximize: $\sum_{i=1}^{M}v_i x_i$

subject to: $\sum_{i=1}^{M} w_i x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

The 0-1 knapsack may be reduced to an instance of the original problem. Assume an instance of the original problem, with the following properties of $G$:

$v_i = 0$ for every vertex $u_i$ with incoming arcs.
All vertices have at most 1 incoming arc.

The 0-1 knapsack may be reduced to this instance by the following polynomial transformation:

There are $M$ items, where $M$ is the number of vertices $u_i \in G: v_i > 0$.
The value $v_i$ of each item the value $v_i$ of vertex $u_i$.
The weight $w_i$ of each item is $1+$ the number of reachable vertices from $u_i$.

Explanation:

Since vertices with a non-zero value have no incoming arcs, they may be chosen independently, as there is no possibility for such a vertice to be chosen twice, as a "dependency" of another one. Thus, individual items in the knapsack problem may be mapped to these vertices.
As no vertice has more than 1 incoming arc, no vertice may be reached by multiple vertices. This guarantees that the weights of each knapsack item are independent of each other.

Questions

Have I formulated the original problem correctly, using the mathematical notations? It's been quite some time since I have formally formulated a graph theory problem.
Is this reduction enough to prove that the original problem is NP-hard? I only have reduced the 0-1 knapsack only to an instance of the original problem, not the original problem itself. Does this imply that the original problem is "at least as hard, if not harder" than the 0-1 knapsack?
Assuming that question (2) stands, is my reduction correct?
Alternatively, could I demonstrate my case via another reduction?


texts:
I was looking through my notes on domain relational calculus, and noticed an interesting result in a question about finding the most expensive pizza(s), given a pizza table with schema $\text{pizza}(\underline{id}, size)$. The first idea that came to me was:

$$\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)\}$$

i.e. A pizza which is at least at big as every other pizza is the most expensive. But the answer given was instead:

$$\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land (\text{pizza}(id2, size2) \to size1 \ge size2))\}$$

The subtle change being that the last $\land$ was switched with a $\to$. I tried converting the if/then to $\lnot pizza(\ldots)\lor size1 \ge size2$ to get an intuitive idea on what exactly causes my former answer to be wrong, but can't seem to put my finger on it. Can anyone grok the differences between both expressions, and why the former isn't the answer? Appreciate it!


texts: Use of Big O Notation in a recent paper by Khot et al

texts:
I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).

The following sentence appears in the third paragraph of the very first page:

  "... the fraction of satisfied constraints is at least $\rho(f) + \Omega(1)$"

At the bottom of page two we have a similar notation where GapCSP(f)$_{1-o(1), \rho(f) + o(1)}$ is defined.

It is confusing for me where the "limit" is being taken here. Put another way, what is the number that's varying inside the asymptotic notation?

I would think that maybe the limit is taken as the number of constraints goes to infinity, but the paper specifically mentions that fixed instances of CSP can have a fraction of $1 - o(1)$ constraints satisfied. But what values could be varying within a fixed instance? (page 2 paragraph 2)


texts: Is lazy evaluation required for do-notation?

texts:
Do-notation is most famous by Haskell, which is also famous for having lazy evaluation.

But is lazy evaluation a requirement for implementing do-notation?

In principle, could do-notation be added to imperative languages, such as Java and C++?


texts: Why can't every computation be expressed in the style of MapReduce?

texts:
What are the limitations of map reduce in the sense of the types of computations that they can express? Is Map Reduce "turning complete"?

I have been told that map reduce only works on things that can be expressed in the Map and Reduce framework, but my question is, why can't everything be expressed like that?

This might be the reason why Distributed Shared Memory systems like tread marks or IVY started to exist. So that we could express general programs and deal with them in a distributed computing manner.

Can someone give me an example of a task that can be done in a DMS and one that cannot be in map reduce? Or maybe, is there a formal theorem or proof showing what things can't be done in MapReduce but that a general programing language can do? What are the inherit limitations of Map Reduce and why are they the way it is?


texts: What's wrong with this substitution for master's method

texts:
I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method:
$$T\left(n\right)=T\left(n-1\right)+n^2$$
I did
$$S\left(2^n\right)=S\left(2^{n-1}\right)+\left(2^n\right)^2$$
Thus
$$S\left(m\right)=S\left(\frac{m}{2}\right)+m^2$$
Which using the master's method yields
$$T\left(n\right)=\Theta \left(\left(2^n\right)^2\right)$$
However, the correct answer to this is:
$$T\left(n\right)=\Theta \left(n^3\right)$$
So what was wrong with my substitution?


texts: Why is the Mersenne Twister regarded as good?

texts:
The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list properties of this generator, most of what I can offer is bad:

It's massive and inflexible (eg. no seeking or multiple streams),
It fails standard statistical tests despite its massive state size,
It has serious problems around 0, suggesting that it randomizes itself pretty poorly,
It's hardly fast

and so on. Compared to simple RNGs like XorShift*, it's also hopelessly complicated.

So I looked for some information about why this was ever thought to be good. The original paper makes lots of comments on the "super astronomical" period and 623-dimensional equidistribution, saying

  Among many known measures, the tests based on the higher dimensional
  uniformity, such as the spectral test (c.f., Knuth [1981]) and the k-distribution test, described below, are considered to be strongest.

But, for this property, the generator is beaten by a counter of sufficient length! This makes no commentary of local distributions, which is what you actually care about in a generator (although "local" can mean various things). And even CSPRNGs don't care for such large periods, since it's just not remotely important.

There's a lot of maths in the paper, but as far as I can tell little of this is actually about randomness quality. Pretty much every mention of that quickly jumps back to these original, largely useless claims.

It seems like people jumped onto this bandwagon at the expense of older, more reliable technologies. For example, if you just up the number of words in an LCG to 3 (much less than the "only 624" of a Mersenne Twister) and output the top word each pass, it passes BigCrush (the harder part of the TestU01 test suite), despite the Twister failing it (PCG paper, fig. 2). Given this, and the weak evidence I was able to find in support of the Mersenne Twister, what did cause attention to favour it over the other choices?

This isn't purely historical either. I've been told in passing that the Mersenne Twister is at least more proven in practice than, say, PCG random. But are use-cases so discerning that they can do better than our batteries of tests? Some Googling suggests they're probably not.

In short, I'm wondering how the Mersenne Twister got its widespread positive reputation, both in its historical context and otherwise. On one hand I'm obviously skeptical of its qualities, but on the other it's hard to imagine that it was an entirely randomly occurrence.


texts: splitting of people betwen groups with group prioritiy list per person

texts:
Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group.
Every person has a monotone ranking from highest (most desired) to lowest of all the groups.
Using this list I want to find the "best matching".
"best matching" is when you maximize the "score of the matching".
"score of the matching" is the sum of the group rankings of the people that got matched with the group, i.e. summing the ranking that the people gave to the group which was chosen for them.
I'm also interested in ideas for other "fairness" values for maximization.


texts: Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w

texts:
The aim of this problem is to find a subset (need not be consecutive) of a given set such that the sum is maximal and less than some given number $w$. (Note, we are trying to find a subset that is less than or equal to $w$ and not closest to $w$).

For example, given a set $\{1, 3, 5, 9, 10\}$ and maximum weight 17, the maximal subset is $\{3, 5, 9\}$ since its sum is exactly 17.

Another example: given a set $\{1, 3, 4, 9\}$ and maximum weight 15, the maximal subset is $\{1, 4, 9\}$ since its sum is 14, and there are no other subsets whose sum is 15.

Example with both positive and negative numbers: given a set $\{-3, 2, 4\}$ and maximum weight 3, the subset is the set itself since -3 + 2 + 4 = 3.

I know how to solve it with only positive numbers, but I am struggling to find an algorithm to solve this problem for the general case with both positive and negative numbers. Obviously, my goal is not to use the brute force approach and check every possible subset since the complexity would be $O(n2^n)$.

I stumbled upon an idea on another post that suggested adding a sufficiently large number to every elements in the set and subsequently changing the maximum weight. That is given a set $R = \{ a_1, a_2, ... , a_n \}$, we add some number $X$ (we can pick some number greater than equal to the absolute value of the smallest negative number) to get a set that looks like $\{ a_1 + X, a_2 + X, ... , a_n + X \}$ and change the maximum weight to $nX + w$ where $w$ was the original weight. Now, we have reduced the problem to only non-negative numbers. However, I could not see a way to actually find the subset that was closest to the original weight, but only whether any elements add up exactly the original weight (ie, there is no way to actually find the subset, but only to determine that some subset exists).

Is there any other clever trick like this one to solve the problem for both positive and negative numbers? Any help would be thoroughly appreciated.


texts: How shall I understand the definitions of `let` expression?

texts:
let as used in programming languages is defined in lambda calculus as per https://en.wikipedia.org/wiki/Let_expression#Let_definition_defined_from_lambda_calculus

  The simple, non recursive let expression was defined as being
  syntactic sugar for the lambda abstraction applied to a term. In that
  definition,

  $$ ( let_s \quad x = y \quad in \quad z ) ≡ ( λ x . z )   y $$

let also has another definition in terms of logic, per
https://en.wikipedia.org/wiki/Let_expression#Let_definition_in_mathematics says

  In mathematics the let expression is described as the conjunction of
  expressions. In functional languages the let expression is also used
  to limit scope. In mathematics scope is described by quantifiers. The
  let expression is a conjunction within an existential quantifier.

  $$   ( ∃ x E ∧ F ) ⟺ let \quad x : E \quad in \quad F  $$

  where $E$ and $F$ are of type Boolean.

  The let expression allows the substitution to be applied to another
  expression. This substitution may be applied within a restricted
  scope, to a sub expression.

In the definition $ ∃ x E ∧ F $ by logic,

Are $E$ and $F$ both propositions?
what does $ ∃ x E ∧ F $ mean? Does it mean $ ( ∃ x E) ∧ F$ or $ ∃ x (E ∧ F )$?
what "substitution" does  $ ∃ x E ∧ F $ allow?
how does  $ ∃ x E ∧ F $ relate to the first definition $( λ x . z )   y$ ?

Does language C have similar construct to let?

Thanks.


texts:
The question is quite simple; almost every computer language today provides the $\exp(x)$ function in their standard library to compute expressions like $ke^{-(x - h)^2}.$ However, I would like to know whether this function is the fastest way to compute the above expression. In other words, is there some way to compute $ke^{-(x - h)^2}$ faster than $\exp(x)$ in standard libraries while keeping the result very accurate?
I would like to specify that Taylor series will not work for my application, nor will any other polynomial approximations.
In the end, I wish to compute a series of these expressions, $$\sum^n_{i = 0} k_ie^{-(x - h_i)^2}$$ for some integral $n \geq 0.$


texts: If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment,  M3 moment (M1, M2 and M3 are given), how can I decide at what moment each process will arrive?


texts: How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

texts:
How would the following term in the pure untyped lambda calculus be parsed:
y λx.x y
The relevant conventions listed on https://en.wikipedia.org/wiki/Lambda_calculus_definition#Notation (as well as many texts on this subject) state:

Applications are assumed to be left associative: M N P is parenthesised as ((M N) P)
The body of an abstraction extends as far right as possible: λx.M N is parenthesised as (λx.(M N)) and not ((λx.M) N)

There is no priority specified between these two conventions.
In the case of y λx.x y, if the "applications are left associative" rule is first applied, we get (y (λx.x)) y, and if the "abstraction extends as far right as possible" rule is first applied, we get y (λx.x y). Which one is considered correct, and on what basis?
Observations and thoughts:
I have tried this on some online tools, and this is what I observed:

https://projectultimatum.org/cgi-bin/lambda parses y λx.x y as y (λx.x y)
https://crypto.stanford.edu/~blynn/lambda/simply.html cannot parse y λx.x y (result is a parse error)
https://jacksongl.github.io/files/demo/lambda/ also results in a parse error.

I initially thought that the rule "abstraction extends as far right as possible" was equivalent to specifying that application binds tighter than abstraction. But this assumption may be wrong. Under this assumption, y λx.x y would be parsed as (y (λx.x)) y, since the "applications are left associative" rule would kick in first.


texts: Should I use Dr. Racket for learning Scheme?

texts:
I've been fiddling with software development for a couple of years and in trying to get into the gist of things I came across SICP, which uses Scheme.
Basically what I want to do at this stage is to store exercise/test .scm files for study. Should I use Emac or Dr. Racket ? Or none of those?
Thanks!


texts: Is there an undecidable language that is mapping reducible to its complement?

texts:
Is there an undecidable language A that is mapping reducible to its complement?
If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don't know whether undecidable languages is closed under complement or not.


texts: Generating valid sentence with respect to attribute grammar

texts:
Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood.  To produce a grammatical string, just keep replacing non-terminals with one of their right-hand-side productions until you have only terminals.

The algorithm for determining whether a sentence is grammatical given a standard formulation of an attribute grammar is also well understood.

My question is: Is there a standard algorithm to produce sentences that are grammatical with respect to attribute grammars?

Edit: I am talking about attribute grammars with synthesized and inherited attributes.  Thus, it is possible to generate something not in the language when the synthesized attributes and inherited attributes don't match up.  This occurs, for instance, in checking that a variable is defined before use (https://web.cs.wpi.edu/~kal/courses/compilers/module4/mysa.html).


texts: maximum sum of diameter of tree + leaf removal

texts:
Problem: A tree of n nodes is given. Have a sum variable. Choose the leaves furthest from one and other and add their distance(the number of edges between them) to the sum variable. Now remove one of the leaves. Continue this process to reach the maximum sum.
My solution: The degree of leaf nodes is 1. We perform BFS (breadth first search) on the leaves and find the furthest leaf from each leaf, the leaves with the maximum distance are chosen and their distance is added to "sum".
Problem: I do not know which of the two leaves to remove for continuing the solution.


texts: Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

texts:
In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.):

  Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real variables. Show that REALQUADEQ is NP-complete.

I know how to show NP-hardness, but I'm stuck when it comes to proving that this problem is in NP, in particular how to show that we can describe a solution using a polynomial number of bits.

I did some research and found out that over the complex numbers, it remains an open question if the problem is in NP [1]. It also seems closely related to the existential theory of the reals, which again is not known to be in NP.

Thus my question: Is this problem known to be in NP? And if so, could somebody point me in the right direction regarding the proof.

[1] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.


texts:
Codd's Algorithm converts an expression in tuple relational calculus to Relational Algebra.

Is there a standard implementation of the algorithm?
Is this algorithm used anywhere? (It seems that the industry only needs SQL and variants, I'm not sure about database theorists in academia.)
What's the complexity of the reduction?

 This was posted on SO over a year ago, but it didn't receive a good answer.


texts: Covering a graph with non-overlapping cliques

texts:
I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows:

Every subgraph must be a complete graph/clique
No vertex can be part of two or more subgraphs
Subgraphs that can be merged with other subgraphs while remaining complete cannot exist
When multiple possible complete subgraphs/cliques are present, chose the one with highest within-clique edge weight

Below is an obvious example. Multiple maximal cliques exists, but it is very clear to the beholder which two should constitute the subgraphs.

Community detection are not a good fit (at least the algorithms I've looked into) because they don't enforce completeness within the communities. Furthermore the graphs that I'm working with are quite small and dense, and community detection algorithms will often just find one large community.

My main approach now is thus to find all maximal cliques, and then somehow remove unwanted cliques based on edge weights but I'm at a loss as to what the best approach for the latter part is...

Edit: This is my current implementation

Detect maximal cliques in the graph.
Sort the cliques in descending order based on their minimum edge weight within the clique.
Iterate over the sorted cliques, adding cliques to my result list if, and only if, its member vertices are not present in any already selected clique.
After iteration see if any vertices in the original graph are present in any of the selected cliques.

If all vertices are present, exit.
If not create a subgraph of the original graph containing the missing vertices and repeat 1-4.

This is sort of similar to @kurtosis answer but handles edge weights as well as the case where vertices are left out of the initial iteration.

Edit 2: To clarify what I'm asking (because it might be less obvious after the first edit). My problem remains as described in the first part. After posing the question I've developed a solution as described in the first edit, that seems to get the job done, but it is, in my view, not very elegant. It might be the only way to solve the given problem, but I wouldn't know as graph theory is not my main area. Thus I'm still curious if there are other more efficient approaches to solving the problem.


texts: Prove that there exists an undecidable complementary language

texts:
Some language A ⊆ Σ∗
is called complementary if A ≤m complement of A. How can I show that there exists an
undecidable complementary language?


texts: The impact of caching on the system performance or on the user experience

texts:
I am working on modeling a certain system's cache layer and comparing two algorithms.

One outperforms the other one; it shows the higher cache hit rate (%).

But what is important is the impact of such an improvement at cache layer on the entire system performance and on the user experience.

The system performs message deliveries from producers to consumers.
So the latency would be a good measure of the user experience.

However, because I am new to this area so I am a little lack of the background knowledge on it.

Is there any one who has worked on similar topics?
Could you give me reference papers to get some understandings on what kind of measure can be used, how those can be represented, ... etc.

(For example, a paper with title "Improving Web Caching System by Adaptive ABC algorithm" can have such information.)


texts: Does RAM get an indication of data size required

texts:
Pre-information:

I'm sure someone has asked something along these lines, but no matter how I word it, I can't seem to find a definitive answer

Question:

Does RAM get some kind of indication as to how much data the CPU requires or is there a set amount of data and if the CPU needs more, it needs to call again (and what is that set amount of data).

During a cache miss, the CPU will require at least a single cache line (32, 64 or 128 bytes). Does the CPU need to query RAM multiple times to get a single cache line (assuming the set amount is 8 bytes) or does the RAM return more data per call or does RAM have some way of being notified as to how much data is required?

I'm aware the CPU is most likely going to call more than just a single cache line to avoid the lengthy request from RAM if more data is needed in future from the same block of memory.

Extra Points:

If you do know and have more information, the following extras would also interest me:

If this is different depending on CPU make (generational differences can also be interesting but if you do add information about that, please skip similar generations)
If this is different depending on RAM type
How the CPU can request a different sized cache line or block size (only applies if RAM returns a fixed size that's the size of a block or cache line)
Any other useful relevant information or resources for further reading

Potential answer:

I seem to have found a clue to the answer when looking at the transfer rate of RAM, specifically where it indicates how to calculate the transfer rate from the specifications and from "DDR SDRAM prefetch architecture" which indicates how many 64 bit "blocks" can be requested per call to RAM (e.g. 8 for DDR3 and DDR4, 4 for DDR2 and 2 for DDR1)


texts: Is deletion and insertion easier in B+ trees compared to B trees?

texts:
I saw this question in test. It says that insertion and deletion is easier in B+ tree compared to B tree. The given reason for this was the key to be deleted must be present in leaf node in B+ tree but the it could be anywhere in case of B tree.
But what i think is, for deletion in B+ tree, we have to go all the way down to leaf and then after deleting, the effect could propagate all the way up to root (merging and redistributing could be required at each level). Instead, if it would have been B tree, we could have found the required key without going all the way down to leaf and its effect could propagate up from their. Didn't we required less work in B tree as compared to B+ tree.


texts: Prove EXPTIME \ NP is not a subset of NP-Hard?

texts: If we assume that NP is not equal to co-NP, how do we show that EXPTIME \ NP is not a subset of NP-Hard?


texts: Showing that u#v with u a substring of v is not context-free

texts:
I need to find whether this language is context-free or not:

{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}

I suspect that it's not, and am trying to approach it via Pumping Lemma, but then I noticed that: any examples like a^n#a^n will not work, cos we can always make vwx in the second a^n such that after pumping, u is still a substring of v; then I tried playing around with # like a#ab^(n-3), but get lost with the choice of v and x since it's possible for one of them to be empty string.

This is homework so just a hint will be okay for me.


texts: Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval

texts:
Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair?

The naive approach is very straightforward, but has O(intervals) test performance:

list intervals (min, max)

func testVal(val){
  foreach (interval(min, max) in intervals)
    if (val > max) || (val < min) return false
  return true
}

In the problem I'm facing the list is not updated frequently, but it is tested against with very high frequency.

Thus, it's acceptable for updating the list to be expensive, but tests need to be sublinear, ideally constant time.

One option is to insert every value in the intervals into a hashtable, but this is memory-intensive and not practical when the intervals get large. Memory usage needs to be proportional to the number of intervals, not the sum of the sizes of the intervals (probably ok to have a log(n) memory usage term thrown in if it greatly aids performance).

I've started poking around with various tree-based options to make this better, but it feels like a general enough problem that I suspect there is preexisting work I should be referencing. Are there any existing solutions to get sublinear tests (ideally constant time) on a list of intervals by preprocessing them into some other datastructure(s)?


texts: how many parameters do we need to estimate for a general probabilistic model

texts:
Its a question from a test in machine learning.
I have 3 binary variables x1,x2 and x3 (which means that each one of them can be either 1 or 0), each one of them has a binary output y (can be 0 or 1).
for a general probabilistic classifier (it could be any probabilistic model except that its not a model that relies on Naive Bayes), how many parameters do we need in order
to estimate it?
you cant assume Naive Bayes independency

I saw that the answer is 16 but I dont know why
I want to clarify that when I mean parameters I mean which Probability I will need such as P[Y=1] or P[X1=1|Y=1] ect'


texts:
Consider below two languages

$L_1=\{<M>|$ M is a turing machine, $M_0$ is a TM that halts on all inputs, and $M_0 \in L(M) \}$

$L_2=\{<M>|$M is a TM, $M_0$ is a TM that halts on all inputs, and $M \in L(M_0)\}$

So, in both languages $M_0$ is a halting Turing machine, so the language of $L(M_0)$ is recursive.

Now in case of $L_1$, it appears to me that $L(M)$ is recursively enumerable, and since recursive languages are proper subset of Recursively Enumerable languages, so $M_0 \in L(M)$ , and since, for the no cases of the language, our turing machine could go into infinite loop, we cannot answer the no case of $L_1$, making $L_1$ Recursively Enumerable but not recursive.

In case of $L_2$, our given machine $M \in L(M_0)$ so it is very sure that the language  $L(M)$ should be recursive.

Am I correct in my reasoning.?

PS: I am weak at these RE and REC problems.So, I decided to work on them and discuss my doubts here.None of the above problems are homework problems.


texts: Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?

texts:
The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and pick the best sequence of moves so far.

Let's suppose we remove this limit, and we search for the whole tree. Would this techinque always win? If the answer is no, would it ever lose? (so, would it only win+draw, or also lose?)

A good answer would include theoretical underpinnings of why or why not this would work, both from the game-theoretic aspects of chess and from the proprieties of the minmax algorithm.


texts:
In Booth's bit-pair recording technique how to multiply a multiplicand with -2 or 2? For example while multiplying 01101(+13, multiplicand) and 11010(-6, multiplier), we get 01101 x 0-1-2.

How to multiply the multiplicand using -2?


texts: Optimal bounding boxes selection for $N$ rectangles

texts:
Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$.  Each rectangle has a cost function, its area  $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into their bounding box. In this case the cost function will be the area of the bounding box, instead of the sum of their areas.

The optimization problem is:

Let $R = \{r_1,r_2,\ldots,r_n\}$

Let $p = \{R_1, R_2,\ldots,R_k \} $ be a partition of the set of rectangles such that $ \forall i,j : R_i \cap R_j = \emptyset  $ and $ \cup R_i = R  $

Then, the following functional should be minimized:

$f(p) = \Sigma  A(R_i)  $, where $ A(R_i) $ is the area of the bounding box of the subset.

I would like to find a fast algorithm that finds the optimal solution.

For example: In a special case of two squares $(x,y,s,s),(x',y',s,s) $ with same area, there are only 2 options, merge or not merge. It is better to merge when the area of the bounding box is smaller than the sum of the areas, $ (x'-x+s)\cdot (y'-y+s) \le 2s^2  $. This happens when these two squares have a sufficient overlap.

A naive algorithm would be checking every possible partition and choose the best. It will take an exponential amount of time.

At first I thought of this simple iterative algorithm:

  For every pair of rectangles $r_i,r_j$

  If merging them will improve the functional,

  Merge them, and update the set of rectangles

  Until there isn't any pair that will improve the functional

But then I found a counter example in which this algorithm will not find an optimal solution:

Merging any two rectangles in this example will not improve the functional. But merging all of the rectangles into one bounding box will be the optimal solution.

I am currently thinking of sorting both the $x$ and $y$ coordinates and attempting to choose a pair of points on this grid, and to check whether it is advantageous to merge all rectangles inside it.

So my questions are:

Is it a known problem in computational geometry?
Can this problem be proved to be NP hard?
Is there any good practical heuristic to solve it?

Note: The same question was also posted on math.stackexchange, but I was unable to get any good answers.


texts: Why computer science papers rarely use advanced mathematics?

texts:
I am a M.Sc. student in computer science, working on information networks and recommender systems. This days when I went through the top-tier conferences papers in the field I have seen most of them use solely simple machine learning tools such as generalized linear model, Expectation Maximization, Maximum Likelihood, etc.

One may argue that this simple methods work better and We shouldn't take the blame for the sake of simplicity. That is true but I have not even seen an interest to try compare their results with some more advanced mathematical methods.

I am wondering why scientists don't try to explore more mathematics to involve in their research. Because there is not something better in exploding world of mathematics or because of its difficulty, etc?

Edit: I mean the areas that are more related to continuous mathematics than CS theory.


texts: Dijkstra's algorithm runtime for dense graphs

texts:
The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges.

Since $E \sim V^2$, is the runtime $O((V+V^2)\log V)$?


texts: Simple cycles of length two in an undirected graph

texts:
Pedagogical question.

Background

A cycle in a graph can be defined as a sequence of vertices $v_1,\dots,v_n$ with $v_1=v_n$ such that, for each $i \in \{1,\dots,n-1\}$, the graph has an edge $(v_i,v_{i+1})$. (One can define it differently.)

The point

Every definition of simple cycle I have seen is: a cycle with no repeated vertices, except the first and last.

But this definition implies that even in undirected graphs, we can have simple cycles of length two, e.g. $u \to v \to u$. However, we probably do not want to consider this a simple cycle because it re-uses the edge $(u,v)$ and this would break several algorithms and proofs.

Of course for cycles of length $3$ or more, requiring no repeated vertices implies there are no repeated edges.

The question

Which of the following is right? Justify your answer.

(1) The standard definitions are incorrect, they ought to explicitly exclude simple cycles of length 2 in undirected graphs.

(2) The standard definitions are correct, the cycle of length 2 is simple.

(3) This question is wrong in claiming this is the standard definition of simple cycle. There are other better definitions that are standard (references please!).


texts: Paging only for user code. What about kernel code?

texts: Why is paging done only for user code (user space)? I know that the basic intuition behind paging is for managing larger logical address space in smaller physical main memory space. Won't the kernel size also be large? If the kernel code is large enough and the RAM size is small, then how is it managed? Please clarify.


texts: Regular language as finite union of periodic sets

texts:
Is it true that every regular language can be expressed as a finite union of periodic sets?  In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that

$$L = A_1 \cdot B_1^* \cup \cdots \cup A_n \cdot B_n^*.$$

I know this is true for regular languages over a unary alphabet, but I'm not sure about general alphabets.


texts: How come Datagram Packets between same source-destination pair may take different routes?

texts:
This might be a rookie question, but I wanted to understand the following line.

My book says, each time a host wants to send a packet, it places the address of the destination host in the packet's header. Okay, I understand this.

Also, packets forwarded using destination address have their address mapped to an outgoing interface. Packets between same source destination pair may take different routes.

Why is that? If packets have the same destination address should they not be mapped to the same outgoing interface?

Is there something I have left out or not understood that is leading to this confusion or is there an explanation to this!


texts: Extract Tree from multi-edge undirected graph

texts:
I have the following multi-edge, undirected graph.

I would like to extract the following tree from it, if I start from the node $A$.

Do you know of any algorithm that I can use to achieve that ?

The problem I am trying to solve is the following.

The first graph represent different relational tables I want to join. Each edge $e_i$ represents one join between two tables (two tables could be joined on different fields, for example).

From that graph, I need to create the tree depicted in the second figure. That tree is then used for executing the joins.

Thanks


texts: Efficiently compressing and decompressing an array of combinations

texts:
I'm wondering if there exists a way to efficiently compress an array containing combinations ${n}\choose{k}$, so that it can be easily decompressed minimizing the data read from that array. An example of such compression would be a using a sliding window:
[1, 2, 3, 4]
---[2, 3, 4, 5]
------[3, 4, 5, 1]
...
Using a sliding window, we would be able to compress the array as follows: [1, 2, 3, 4, 5, 1, ...]
Another solution could be swapping 1 element each time using a certain pattern, starting from a single combination.
[1, 2, 3, 4]
          |
[1, 2, 3, 5]
       |
[1, 2, 4, 5]
    |
[1, 3, 4, 5]
 |
[2, 3, 4, 5]
          |
[2, 3, 4, 6]
This way we can save the array in a similar way, since we know each time what position to swap: [1, 2, 3, 4, 5, 4, 3, 2, 6, ...]
The order of the combinations does not matter, as long as each combination is in the array exactly once. The order of the elements of the combinations does not matter either. I'm also fine with using other representations of the combinations such as bitvectors.
I am aware of algorithms to generate the combinations, which is my backup plan if this is not working.
My goal is to read the combinations multiple times, but I would like to minimize the data to be read from memory. Therefore I would want something like a sliding window that reuses part of the last solution and reads a minimal amount of new data.


texts: Can an NP-hard problem be polynomial on average?

texts:
I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this?

If $P \neq NP$, can there be an algorithm solving an $NP$-hard problem with amortized (average case) running time of $O(n^k)$ for a constant $k$?
Are there any problems which are $NP$-hard which are also in $BPP$, or even $PP$?

Can anyone answer or provide a reference answering either of these questions?


texts: What is the optimal solution to prove the reachbility of a node from the root?

texts:
I have a finite automaton with these properties:

Contains cycles
It's a directed graph
All the states/nodes are initialy reachable from the initial state
It has final states but I guess it isn't relevant for my issue
It's a random generated automaton, and the generation isn't meant to satisfy properties like strongly connected components or connected components

Let's suppose I have to delete an edge.

I need to know if there's a way to prove that the reached state by this edge is still reachable from the initial state without using a classical search (DFS or BFS); obviously, if there is any.


texts: Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP

texts:
I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP.
The equation has total n variables and each clause is a 2SAT equation in itself in a subset of variables from 1 to n.
Example:
F = [(x1 || x2 ) && ( !x2 || x3) && (x3 || x4)] || [(x2 || x5) && (x3 || x6) && (!x4 || !x6)] || ....
The equation F is a DNF of 2SAT equations, which has say m clauses. Is finding a solution to this in NP? If yes how?
Also, specifically I also want to know if finding False instances of equation F is in P or NP as well.


texts: Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

texts:
$P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$ are known and usually handwaived as exercises. I could not find proofs of these two results.

What is a rigorous proof for $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$?

How is having an oracle to $\#P$ at most as powerful as having an oracle to $PP$?


texts: Proof that language is not context-free with Parikh's theorem

texts:
I want to prove that the language $L = \{ a^{n}(ab)^{{n}^{2}}b^{n} \mid n \geq 0 \}$ is not context-free by using Parikh's theorem.

My first assumption is that the $(ab)^{{n}^{2}}$ part cannot be written as a subset of linear vectors.
From this it follows that $\psi(L)$ is not semi-linear.

My problem is to show that by a formal proof.


texts: Decidability of Equality of Radical Expressions

texts:
Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).


texts:
I am interested to know whether the time complexity of following algorithm is  $O(n^2)$ or $O(n\log n)$.

Here is the implementation:

public class HelloWorld
{

 public static void main(String[] args)
 {

    Hello hw = new Hello();
    int[] n = {2,3,4,52,5,63,0,664,2,2,56,68,8};
    hw.sortUsingDLLWODup(n);
 }
}

public class Node
{
   public int value;
public Node next;
public Node prev;
public Node(int v) {
    value = v;
}
}

public class Hello
{

public void sortUsingDLLWODup(int[] n) {

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0;i<n.length;i++) {
if(max<n[i])max = n[i];
if(min>n[i])min = n[i];
}

Node root = new Node(min);
Node end = new Node(max);
root.next = end;
end.prev = root;

for(int i = 0;i<n.length;i++)
{
    Node current = root;
    while(n[i]>current.value && current!=null) {
        current = current.next;
    }
    if(current!=null&&current.value>n[i]) {
        Node temp = current.prev;
        Node newNode = new Node(n[i]);
        temp.next = newNode;
        newNode.prev = temp;
        newNode.next = current;
        current.prev = newNode;
    }
}
Node test = root;
while(test!=null){

System.out.println(test.value);
test = test.next;
  }
}
}


texts: Lexicographic Order of Expression [Automata Theory]

texts:
what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order?
I'm confused and I really want to clear my concepts so I can proceed further


texts: How to deal with questions having two or more asymptotic notations

texts:
The following was asked as part of a homework assignment and I am not asking for the solution to these but rather tips or resources on how to solve this and similar questions,

Let $f(n)$ and $g(n)$ be two functions from $\mathbb{N}^+$ to $\mathbb{R}^+$. Prove or disprove the following assertions. To disprove, you only need to give a counter example for functions $f(n)$ and/or $g(n)$ which make the assertion false. Consider the following.

$$\Omega(\Theta(f(n))) = \Omega(f(n))$$

According to me the answer is false in this case, my reasoning is that whenever we say $f(n)=\Theta(g(n))$ we are saying that $f(n)$ will always lie between the limits of $g(n)$.
Here, let's say $x(n) = \Theta(f(n))$ so it will always lie between the function $f(n)$ then we take $\Omega(x(n))$ which would mean that $y(n)$ will always be greater than $x(n)$, and on the right hand side we compare it to some $a(n)$ which is equal $\Omega(f(n))$ meaning that $a(n)$ will always be greater than $f(n)$. Hence we cannot say correctly if the relation will hold, it may or may not be true.

Is this the correct way of looking at the problem, is there a better way to solve these questions?


texts: Randomly generating graph based off number of connections on each node

texts:
I'm trying to generate a graph based off some data I have.
This graph should have N nodes where the number of edges each node has is equal to a random number P(k), where k is the "index" of the node (mostly arbitrary).
My question is, is there an actual way to do this? I'm thinking that I need more data that either determines the density or another degree of connections out (N1->N2->N3), but I'm not entirely sure.


texts: 01 Knapsack with selection of items with minimum total weight

texts:
I have a slightly modified version of a classical 01 knapsack problem. Specifically, the problem has an additional constraint which requires that if more than one feasible selection with equal value exists then the selection with minimum total weight be selected. For example, consider a knapsack with size 3 and the following set of items to choose from; tuple is defined as ("name", weight, value):

items = (("alpha", 3, 4), ("beta", 1, 3), ("gamma", 1, 1))

There exist two possible selections with total weight <= 3 and value = 4:

Selection 1:

[alpha] with a total value of 4 and weight 3

Selection 2:

[beta, gamma] with a total value of 4 and weight 2

Due to the additional constraint, selection 2 is the correct answer. However, the classical 01 knapsack doesn't ensure this. So my question is, does there exist a variant of 01 knapsack which handles this? If not how do I tackle this additional constraint.

So far, I have the following two approaches which can possibly work:

Calculate the density of the objects and then perform knapsack using
density as the value. This approach however is suited to fractional
knapsack where any arbitrary amount of an item can be taken. In this
case, the item, if taken, must be taken in its entirety.
Sort the items with respect to weights before running knapsack on
them.


texts: Succinct bounded-sum array with $O(1)$ access

texts:
Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$.

Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written in $O(1)$ time), and that $M=n^{O(1)}$.

A standard implementation could allocate $\lceil \log_2 M\rceil$ bits per cell, resulting in a $n\cdot \lceil \log_2 M\rceil$ bits array.

Arithmetic encoding allows us to encode the array using
$$\left\lceil\log_2{n + M \choose M}\right\rceil\approx n\log\left(\frac{M}{n}\right)$$

bits, but does not allow $O(1)$ time operations.

  Is there a succinct encoding (say, of size
  $n\log\left(\frac{M}{n}\right)+O(n)$) that allows $O(1)$ time
  operations?

The required operations are standard array operations -- retrieving and setting the value of $A[i]$ for any $i\in[n]$.


texts:
I am trying to find some generic upper bounds on the "standard" graph partitioning problem.  Say I have a graph with $|V|$ vertices and $|E|$ edges  I want to partition it into two equal $N/2$ (or approximately equal if easier) parts while minimizing the cut i.e.  $\min(|C|)$ where $C$ is the set of edges with nodes on either side of the partition (similarly nodes that the cut goes through).
So far this is standard stuff and clearly the optimal solution depends on the details of the graph. However, what I want is an upper bound on $\min(|C|)$ in terms of $|V|$ and $|E|$ without knowing anything else about the graph. If no upper bound then even some type of average case estimate would help.
Also, the same thing for a multigraph.


texts: Transforming an immutable binary tree without recursion

texts:
I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case replace the node with a new node. Nodes are immutable. So when I encounter something I have to change, I have to return the new version of the node all the way up. Ultimately the root changes. Specifically I'm trying to implement the RESTRICT algorithm for ROBDDs.

And I have! This works fine (C#, sorry?)

        Node Restrict(Node node, Func<Variable, bool?> npoint)
        {
            if (node == context.Term0 || node == context.Term1)
                return node;

            // value has been restricted, replace with true or false path
            if (npoint(node.Variable) is bool value)
                return Restrict(value ? node.Hi : node.Lo, npoint);

            var lo = Restrict(node.Lo, npoint);
            var hi = Restrict(node.Hi, npoint);
            return new Node(node.Variable, lo, hi);
        }

However, my diagram is rather huge. And I'm running out of stack space.

So, I'm trying to come up with a way to do this without recursion. I've tried a few things but haven't come up with anything that works. As I start to expand it out, it gets pretty complicated and I start losing track of stuff.

Can somebody point me to some resource on this?


texts: How to analyse the time complexity of an algorithm based on the input values in addition to input size

texts:
I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input value in addition to the input size.
The joke algorithm was this sleep sort algorithm in javascript
const arr = [20, 5, 100, 1, 90, 200, 40, 29]

for(let item of input) {
   setTimeout(() => console.log(item), item)
}

// Console Output
1
5
20
29
40
90
100
200

If we were to describe its Time Complexity and only took into consideration the size of the input, it would be O(n). But from a practical standpoint that wouldn't be really accurate as the Worst Case Time of the implementation is heavily dependent on the actual value of each array element, so is it possible to convey this in a Time Complexity Analysis notation? Is there such a thing as O(max(n) + n), for example?


texts: How to find an IP in overlapping ranges of IPs?

texts:
I have a large number (millions) of IP ranges which might overlap. An IP range should contain the start IP, stop IP and an range id. How can I efficiently find which ranges contain a given IP?

I could iterate over all the ranges and check for every range if it contains the IP, but I'm looking for a complexity better than O(n).


texts: Dynamic Programming Recursive Algorithm - Number of heads in a series

texts:
So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic Programming to do this and I'm having a hell of a time identifying the recursive algorithm for this.

My first thought was a bottom up approach where I start from a singular toss and then increment a variable whenever I find a sequence that has three heads in a row and then subtract that number from the total number of possible permutations to get the answer but I'm having trouble implementing the logic behind that.

I see that instead of thinking increasingly large sequences, it would be better to think of each individual toss in the sequence. Mostly what I'm having trouble with is how I should be keeping track of all this.

For example, the first toss is a H, that affects the rest of the sequence because I can't have 2 more H's consecutively, but if the first toss is a T, that doesn't affect the rest of the sequence. So, do I wait till the third toss to tell if I increment? Do I discard the first toss if it's a T? I'm having quite a bit of trouble visualizing and comprehending this problem.


texts: Numerical ratio between the length of a string and the transited states

texts:
If we have a finite automaton that accepts a string,

is there any numerical relationship that always is true like S ≥ |w| or something similar?

Where |w| the length of the string and S the number of transited states (counting multiplicities).

For example, if we have this automata and the string w = 010 :

S = 3 and |w| = 3.

In this case, S = |w|

I'm new in computer science and i was thinking there has to be a rule of that kind but I have not found explicitly in the books that I started on computational theory.


texts: Landau Notation: Why is O(f) (not) the set all g < c*f?

texts:
I am somewhat confused here about the Landau notations. Let's say we are dealing with function from $\mathbb{N}$ to $\mathbb{R}$. Then we can define $\mathcal{O}(f) = \left\{ g : \mathbb{N} \to \mathbb{R} | \exists c > 0 \text{ such that } g \leqslant cf\right\}$. Ok, so every function $g$ that is asymptotically smaller than $f$ is in this set. So if we have an algorithm $A$ that runs at most exactly $n^2+10$ steps, then
$g1 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n^2 \in \mathcal{O}(A)$.
But also
$g2 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n \in \mathcal{O}(A)$
or even
$g3 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto 0 \in \mathcal{O}(A)$
satiesfy the condition to be elements of $\mathcal{O}(A)$. So, why would normally only $g1$ be the function of which one would say $g1 = \mathcal{O}(A)$ ?
I understand the $=$-sign is formally incorrect and just a convention, but if $g2$ and $g3$ also are in $\mathcal{O}(A)$ why define $\mathcal{O}$ this way, if $g1$ is the only function we care about to describe the asymptotic complexity of $A$?
Edit
So, I see I had misunderstood the idea a little. So far I thought $\mathcal{O}$ would take an algorithm and return how long it runs asymptotically. So, what $\mathcal{O}$ actually does is the following>:
If we have an algorithm $A$ saying that
$$\forall c > 0. \forall x \in domain(A).\lim_{n\to\infty} T(A(x)) \leqslant cn$$ would be the same as $$T(A) \in \mathcal{O}(n)$$
Is that correct?? Something looks still wrong about that.
($T$ being the function that returns the number of steps the computation required.)


texts: How complete directed graph with n-vertices is connected to the n-dimensional simplex and its triangulation?

texts: Answer https://stackoverflow.com/a/26151549/1375882 suggests that Sperner's lemma can be used to prove the existence of index for the search Hamiltonian path in complete directed graph. But Sperner's lemma is about simplex, its triangulation and colouring. How such notions can be mapped to the complete graph with n-vertices?


texts:
how can i prove that T(n)=T(n-2)+T(n-3)+T(n-4)+2  is O(logn)?
or T(n)=T(n-1)+T(n-3)+1 the same..
when T(0)=1 T(1)=2 T(2)=3 T(3)=5 T(4)=8 etc`..

it's a Q about AVL-2 tree,the same rules of AVL tree who rotate after 3 levels diff between L,R childs.. and not 2 as AVL tree

thanks for all.


texts: Isomorphisms between regular graphs of same degree

texts:
Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G_1| = |G_2|$)?


texts: Recurrences and Generating Functions in Algorithms

texts:
Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex cover set in a graph might just inspect all $\binom{n}{k}$ possible subsets. While the binomial functions grows exponentially, if $k$ is some fixed constant we end up with a polynomial time algorithm by asymptotic analysis.

Often times real-life problems require more complex combinatorial mechanisms which we may define in terms of recurrences. One famous example is the fibonacci sequence (naively) defined as:

$f(n) = \begin{cases}
   1 & \text{if } n = 1 \\
   0 & \text{if } n = 0 \\
   f(n-1) + f(n-2) & \text{otherwise}
  \end{cases}
$

Now computing the value of the $n$th term grows exponentially using this recurrence, but thanks to dynamic programming, we may compute it in linear time. Now, not all recurrences lend themselves to DP (off hand, the factorial function), but it is a potentially exploitable property when defining some count as a recurrence rather than a generating function.

Generating functions are an elegant way to formalize some count for a given structure. Perhaps the most famous is the binomial generating function defined as:

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Luckily this has a closed form solution. Not all generating functions permit such a compact description.

  Now my question is this: how often are generating functions used in design of algorithms? It is easy to see how they may be exploited to understand the rate of growth required by an algorithm via analysis, but what can they tell us about a problem when creating a method to solve some problem?

If many times the same count may be reformulated as a recurrence it may lend itself to dynamic programming, but again perhaps the same generating function has a closed form. So it is not so evenly cut.


texts: Imposing sortal restrictions on functions in the untyped lambda calculus

texts:
In the simply typed lambda calculus if we have an addition operator, $+ : n \to n \to n$, its typing imposes that we can only combine it with something of a given type. So if $n$ is the type of natural numbers, we can only combine $+$ with things of type $n$.
In the untyped lambda calculus can we invent a function which only allows us to combine two numbers together, computing their sum?
I thought that in the untyped lambda calculus if we have a function $\lambda x,y. add \, y \, x$ then $x$ and $y$ could be substituted for by anything. For example, if we had a constant $John$ which denotes a human being named `John', then we could derive:
$$\lambda y. add \, y \, john$$
If we want $add$ to be a function on numbers and not humans, how is this ruled out in the untyped lambda calculus?


texts:
Let $G=(V,E)$ be an undirected graph. I would like to maintain information about the connected components of this graph(I want to be able to tell in what component particular node is lying). The graph operations are the following (basically, everything except vertex deletion):

Add vertex
Add edge
Delete edge

What are the state-of-the-art approaches to this problem? I know about various algorithms solving dynamic connectivity problem with $\mathcal{O}(\log^2(n))$(which is great complexity for me) update cost, but in my case, I want to add vertices too.


texts: Writing a linear program to model balanced bin packing

texts:
Say we want to write a (MI)LP to model the following problem:

  Find a parking plan for a set of cars $K=\{1, ..., k\}$ with lengths
  $\lambda_i$. Parking is organised in lanes $P=\{1, ..., p\}$. The
  length of a lane is the sum of the cars parking there and may not exceed a specified constant $L$. The goal is to balance the lengths of
  the parking lanes as well as possible. More specifically, we want to
  minimise the difference of the length of a longest and shortest line.

To me, this seems quite akin to some variant of the Bin Packing problem. Usually, however, we want the number used bins to be minimised.

Here, I am quite confused on how I could come up with an objective function that expresses the balance between the lanes/bins. My main problem is that -- as far as I understood it -- the objective function has to be linear. Thus, I couldn't use operations like max, min, absolute value etc.

Can someone help me out here with a hint?


texts:
Consider a bipartite graph with vertex set partitioned into $X=\{u_1,u_2,u_3\}$ and $Y=\{v_1,v_2,v_3\}$. Consider the graph has the following edges: $\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_2,v_3\}$, $\{u_3,v_2\}$ and $\{u_3,v_3\}$. The perfect matchings are $\{\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_3,v_3\}\}$ and $\{\{u_1,v_1\}$, $\{u_2,v_3\}$, $\{u_3,v_2\}\}$. The total number of such matchings is $2$.

However I do not want the same edge to occur in two different sets. Here edge $\{u_1,v_1\}$ occurs in both the sets. So I can pick one of the two possible matchings for a total of $1$.

Is there any counting strategy for the new matching problem? Note that permanent counts perfect matchings in the base case.

Is there an approximation algorithm?


texts:
I need to calculate the complexity of func5, depending on variables $n, m$.

func4 is a function whose complexity is $\Theta(n+m)$

void func5(int a[], int n, int m, int b[])
{
    if (n==0) { return; }
    *b = func4(a,n,m);
    func5(a+1,n-1,m,b+1);
}

I get an expression which looks like:

$$C_1*n + C_2*(nm+n^2) - C_2(1+2+3+..n)$$

$C_1$ is the operations done in each iteration of func5,
$C_2$ is the operations done in each call to func4,
and the substraction comes since func4 is receiving each time a smaller $n$ by one.

The answer says that complexity is $\Theta(n*m+n^2)$ but I don't understand how to find the constants leading to Big-Theta notation.

Thanks.


texts:
This seems like a question that should have an easy answer, but I don't have a definitive one:

  If I have two $n$ bit numbers $a, p$, what is the complexity of
  computing $a\bmod p$ ?

Merely dividing $a$ by $p$ would take time $O(M(n))$ where $M(n)$ is the complexity of multiplication. But can $\bmod$ be performed slightly faster ?


texts: Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score

texts:
Question:  Suppose you are a given a csv with N lines of the form StudentID, score.  Multiple lines can have same student-ID.  Find the student with maximum average score

I can't think of any way to make it faster than O(N*logN).

Maintain a hash-table that keeps track of STudentID = Key and Value being an object with sum of scores and number of scores seen with that studentID --> O(N)
Create an array with values in hash table, maybe convert each entry into average while doing so
Sort it worst-case N(logN), all entries belong to same student

Is there any way to do it faster?


texts:
I'm studying for my finals and I can across this statement.

"For a fixed set of (unique) keys, any binary search tree containing those keys can
be converted to any other BST on the same set of keys via a sequence of left- and/or right-
rotations."

I'm interested in a proof. Does anyone know any references?


texts: Asymptotic notation between two sets of variables

texts:
I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't actually understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.
If for example I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.
Another idea was to assume that both $n$ and $m$ are a function of some unknown variables that depend on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.
Is this right? Am I missing something?


texts: Applications of derivative only, zeroth-order free optimization

texts:
I understand what is derivative-free optimization, and I am thinking a similar problem where the function $f$ we are optimizing is unknown and the only information we can acquire is the derivative. In other words, we can get $(x_1, \nabla f(x_1)), \cdots, (x_n, \nabla f(x_n)$ to optimize the unknown function.
I know the current gradient based optimization tasks in machine learning are all using this idea to optimize the loss function. But as far as I can understand, all of those problems require the predefined loss function, and compute the gradient based on the predefined loss function at each time step $t$.
Are there any real world problems which don't have such a predefined loss function but give you the gradient of the function you are optimizing directly? In other words, you'll optimize an unknown loss function $f$, at each time step $t$, you choose $x_t$ and receive $\nabla f(x_t)$ as the feedback.


texts: Is the difference between two regular expressions a new regular expression?

texts:
Let say the following:

Given Ax and Bx two literals which represent POSIX regular expressions.

Let def A as the set of literals that match Ax. The same def for B.

Using relative complement operation, is there always regular expression for $A/B$ set, for every pair of Ax,Bx?

I attach an example:

Ax := a.*
Bx := a.*b$
// The difference A/B would be
Cx := a.*[^b]$


texts: Peterson Algorithm for process synchronisation

texts:
Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

repeat

flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then
exit critical section
Flag[i] = false;
Perform other non-critical section actions.

Until false;

For the program to guarantee mutual exclusion, the predicate P in the while loop should be

a) flag[j] = true and turn = i

b) flag[j] = true and turn = j

c) flag[i] = true and turn = j

d) flag[i] = true and turn = i

=============================================================================================

Now, in original peterson algorith, we have -

I'm writing just the important lines from the algorithm and not the whole algorithm -

  1) flag [process] = 1;

  2) turn = process ;

  3) while (interested [other] == True && turn == process);

  4) ///////***CS///////

  5) flag [process] = false;

  out of CS

  Now, according to given question -

  flag[i] = true;
      turn = j; i.e process i is interested as flag[i] = true, but turn = j i.e turn is of process J.

So, which process is exactly currently executing?

Question 1) Process i or Process j

Question 2) Which process are we blocking in while loop i.e stopping to enter CS?

  Also, at exit of CS - flag[i] = false;

  this means, Process i, is already in CS?

Now Pi is already in CS, this means, process j is executing and we should hold it in while loop and not let process j eneter CS.

  So, according to know peterson algo I mentioned above -

  line 3) while (flag [other] == True && turn == process);

  while(flag [i] ==true && turn = j);

  both are true so, while loop is true and process Pj should spin here
  and not go to CS.

  and this matches with option c. but answer is option b)

  Also, folks are saying that option c) will allow both Pi and Pj into
  CS.

May you guys please explain, how option b) is answer!


texts: Linear-time algorithm to find an odd-length cycle in a directed graph

texts:
Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by  S. Dasgupta, C. Papadimitriou, and U. Vazirani.)

The related post@cs.stackexchange asks for the existence of an odd-length directed cycle in a digraph, which is solved by the following theorem@algs4.cs.princeton.edu.

  Theorem: A directed graph has an odd-length directed cycle if and only if one (or more) of its strong components is non-bipartite (when treated as an undirected graph).

Thus, we can assume that the digraph is strongly connected.


texts:
I need some help understanding the problem statement in CLRS 11.3-4 pg 269.  It says:

  Consider a hash table of size $m = 1000$ and a corresponding hash function
   $ h(k) =\left \lfloor m(kA \bmod 1) \right \rfloor $
  for $A = (\sqrt5 - 1)/2$. Compute the locations to which the keys
  61, 62, 63, 64, and 65 are mapped.

Is $\mod 1$ a misprint in my copy? Also $A$ is a real number.  Is modulus defined for non-integer numbers?


texts: Proof that {$a^m b^n$ | m!=n} is not regular

texts:
I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's).
How can I formally prove it?


texts: Undecidable language and Turing Machines

texts:
I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about.

  If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine that recognizes the complement of A?

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine. Also seeing as the Language is undecidable, this Turing Machine will not halt for strings that are not in the language.

Can someone please tell me if my understanding is correct or not, and if not give me some clarification?


texts:
I am trying to solve the following problem:
Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of only 0's from it. A 1 in the sheet (represented by the matrix) indicates that we cannot cut the region out from the sheet. Given such a matrix, find the maximum number of blocks which can be extracted.

For instance, if the given matrix is:

There can be 2 blocks which can be extracted out of this.

My Solution:
I am using a greedy algorithm to solve the problem. I traverse from all the corners of the matrix (top-left, top-right, bottom-left, bottom-right) - one by one, extracting out the blocks on a first encountered first extracted basis. Finally I return the maximum of the 4 values that I get. From each corner, I traverse an entire row first (horizontally), only then I move up or down in the matrix.

The algorithm is as follows:

1) Starting from the top-left corner of the matrix (0,0), I iterate along all the columns
in this row from left to right.

2) If a zero is encountered at a position (i,j), I check if this is a possible
contender to be the top-left corner of a 2x2 block consisting of all zeros -
which would be the case when values at (i, j+1), (i+1, j) and (i+1, j+1) are all zeros.

3) If it is, I fill the 2x2 block {(i,j), {i,j+1), (i+1,j), (i+1,j+1)} with 1's, and a
counter is incremented.

4) Steps 2 through 3 are repeated for all rows from the top to bottom.

5) I restore the original matrix in the problem, and start again from the top-right corner
of the matrix (0, N) - N being the number of columns in the matrix, and iterate along
all the columns in this row, from right to left.

6) If a zero is encountered at a position (i,j), I check if this is a possible contender
to be the top-right corner of a 2x2 block consisting of all zeros - which would be the
case when values at (i, j-1), (i+1, j) and (i+1, j-1) are all zeros.

7) If it is, I fill the 2x2 block {(i,j), {i,j-1), (i+1,j), (i+1,j-1)} with 1's, and a
different counter is incremented.

8) Steps 6 through 7 are repeated for all rows from the top to bottom.

9) Likewise, the matrix is traversed two more times from bottom-left and bottom-right
corners, checking for a '0', which can be a possible bottom-right or bottom-left corner
for a 2x2 block consisting of all zeros. Each of these matrix traversals are performed on
the original matrix given in the problem - i.e. changes made in top-left traversal are
discarded while traversing the matrix from top-right and so on.

10) The 4 traversals of the matrix give us 4 different counters, and the maximum of
these 4 values is returned as the result.

So far I have not been able to come with a test case which shows that the algorithm is incorrect. As I am not very good with proving correctness of algorithms, I need some help to figure out if this algorithm is correct.

Thanks!


texts: How to prove the equivalence of two CFG for balanced parentheses?

texts:
Given two CFGs for balanced parentheses.

$S \rightarrow  SS \mid (S) \mid \epsilon$
$S \rightarrow S(S)S \mid \epsilon$

How do I show that they are equivalent?

I have been able to show $ L(2) \subset L(1) $ as follows

$$ S \Rightarrow SS \Rightarrow SSSS \leadsto S(S)S $$

Thus, $ S \leadsto S(S)S $. Keeping production rule $ S \rightarrow \epsilon $, we get $ L(2) \subset L(1) $.

But I can't prove the reverse i.e. $ L(1) \subset L(2) $. Any help would be appreciated.


texts: Determine if an array is divisible in pairs of equal sum

texts:
I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:

Let A be an unordered array of positive natural numbers. Write an algorithm that checks if it's possible to divide A into pairs (subsets of two elements) of equal sum.
Example [1 7 4 2 4 0 8 6] is composed of 1+7, 4+4, 2+6 etc all of which give 8.

Now, the solution works like this: it sorts the array, and then checks if the sum of $A[i]$ and $A[length-i]$ (indexes start at 1) always give the same value.

Example: [0 1 2 4 4 6 7 8] is the above array after reordering. Checks 0+8=8, then 1+7=8, then 2+6=8 etc.

So the algorithm returns True, since every $(n,n-i)$ pair in the array always gives the same sum.
My problem with this is that I can't understand why positioning the elements with this symmetry would give an equal sum everytime.
Why taking the $i$ and $n-i$ elements would give the same sum?


texts: Can we define the Functor Category in Haskell (or any other language with a more expressive type system)?

texts:
Here I am talking about the Functor category, which is defined as a category whose objects are functors and morphisms are natural transformations.

For reference: https://ncatlab.org/nlab/show/functor+category

I was wondering if it is possible to define this in Haskell.

If we define category like this:

class Category cat where
   id :: cat a a
   (.) :: cat b c -> cat a b -> cat a c

Now how do we define Functor as an instance of this, given that Functor is itself a typeclass?

EDIT

I am not tied to the above definition of a Category. I see Edward Kmett represents a Category like this:

newtype Yoneda (p :: i -> i -> *) (a :: i) (b :: i) = Op { getOp :: p b a }

type family Op (p :: i -> i -> *) :: i -> i -> * where
  Op (Yoneda p) = p
  Op p = Yoneda p

class Vacuous (a :: i)
instance Vacuous a

class Category (p :: i -> i -> *) where
  type Ob p :: i -> Constraint
  type Ob p = Vacuous

  id :: Ob p a => p a a
  (.) :: p b c -> p a b -> p a c

I am not looking for Haskell specific implementation, but in any functional language in general.


texts: Construct DFA accepting strings ending with '110' or '101'

texts:
Let the alphabet be $\Sigma=\{0,1\}$. I want to construct a DFA which accepts strings ending with either '110' or '101', additionally there should be only one final state.

I have a solution with more than one final state, but cannot come up with a solution which has only one final state.


texts: Could someone explain Fagin's theorem on the equivalence between NP and existential quantifier

texts:
This quote on descriptive complexity theory is given in Wikipedia:

"The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets."

Is there a simple proof of the theorem?


texts: Upper bound on size of minimal binary coverage code

texts:
Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that every $x \in \mathscr X_n$ is within Hamming distance $\le r$ of some $y \in S$. A minimal $r$-coverage code is one for which the cardinality $|S|$ is minimal. Let this minimal cardinality be $N_n(r)$. Note that we have the trivial bound $N_n(r) \le 2^n$.

Question. What are good upper-bounds for $N_n(r)$ in terms of $N$ and $r$ ?


texts: The length of the smallest co-prime chain between any two integers

texts:
Consider the following statement:

for any $a < b \in \mathbb{N}$, one of the following holds:

$\gcd(a,b) = 1$.
there is a $a < x < b$ such that
$\gcd(a,x) = \gcd(x,b) = 1$.
there are $a < x < y < b$ such that
$\gcd(a,x) = \gcd(x,y) = \gcd(y,b) = 1$.

Is this statement true?

Motivation:
I found a variant of this problem in one of the recent algorithms competitions.
Consider the following problem:
Input: two integers $a$ and $b$ where $a \lt b$.
Output: smallest number $l$ such that there are integers
$a = x_0 < x_1 < x_2 < \ldots < x_l < x_{l+1} = b$ such that
all consecutive integers in the list are co-prime:
$\gcd(x_i, x_{i+1}) = 1$ for $i=0,\ldots, l$.
Examples:

$a = 7, b = 13$:
$\gcd(a,b) = 1$, therefore $l = 0$.

$a = 10, b = 12$:
$\gcd(a,b) = 2 \neq 1$, therefore $l \geq 1$.
Let the sequence be $10, 11, 12$. $\gcd(10, 11) = 1, \gcd(11, 12) = 1$.

$a = 2184, b = 2200$:
There is no $a< x < b$ such that $\gcd(a,x)=\gcd(x,b)=1$.
However, we can find $2$ integers that satisfy this problem.

There is a reference algorithm that algorithms are evaluated against.
That algorithm assumes that

There is always an $l$ that satisfies the condition.

$l\leq 2$.

I don't see why they are true.
I have a polynomial time algorithm that does not assume either of them.
I am not losing out on the asymptotic performance
compared to the reference algorithm,
but I could get the performance constants much lower
if I can understand and prove the validity of the assumptions.


texts: Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$

texts:
Given a circle with $n$ equal segments. On each segment there is an
integer. We want select segments at equal distance, maximizing the sum of integers on selected segments.

I have an algorithm with runtime $O(n^2)$ as follows:
First calculate maximum sum of segments at distance one. Second calculate maximum sum of segments at distance two, and so on. Return maximum of all above values.
According to the teacher, there is a solution with runtime $O(n\log n)$, but I cannot find it.


texts: Undecidability of language involving two TMs

texts:
I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve.

  Given $M_1$, $M_2$ Turing machines, is it true that for every $x \in \Sigma^*$ $M_1$ performs at least as many steps while working on input $x$ as $M_2$ does with input $x$?

There is also an answer to the excercise and a hint, though it didn't help me that much:

Let $M_1$ be a TM which enters an infinite cycle for any input → halting problem (and thus undecidable).
Complement of the language is partially decidable, because non-deterministic TM can provide a counter-example.

In particular, I would like to know how can I express these statements formally:

How to formally describe the language describing the problem?
How to reduce the language to halting problem?
How to show that the complement is partially decidable?

The only thing I can decide with a confidence is that the language itself is not even partially decidable, since complement is partially decidable, but the language itself is not decidable, and thus the language is not even partially decidable (Post theorem).


texts:
There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$:

The goal is to select one of the polygons, say $D_i$, and attach to it a polygon $E_i$ such that:

$D_i\cup E_i$ is still simply-connected.
$E_i$ is interior-disjoint from all other polygons $D_i$.
$D_i\cup E_i$ is connected with the exterior of $C$:

Is there an algorithm, preferably published, that solves this problem in time polynomial in the representation of the problem (e.g. total number of vertices of all polygons)?


texts:
Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings:

102 of A

364 of B

70 of C

I can put 50 molds in the kiln at a time.
I can have 75 molds made in any combination.

First, what is the optimal combination of molds to make.

Second, what is the schedule to make the castings in as few firings as possible.

I am trying to wrap my head around this problem. I see that the second part resembles task scheduling problems I've read about, but I have no idea how to tackle the first problem.

Any help/insight very much appreciated.


texts: Cardinality of the set of all TMs that semidecide a r.e. language

texts:
What is the cardinality of the following set

$M: = { \text{M is a Turing Machine with}  \sum_{i}=\text{{0,1} and LA(M)=L}}$
where $ \text{L is a recursively enumerable language such that } L \subseteq \text{{0,1}}*$

Which means how many TMs semidecide a recursively enumerable language L?

We know that the set of all r.e. languages is countably infinite and that we can encode any TM as a binary number, thus as an integer and therefore we can define a bijection from the set of all TMs to $\mathbb N$. Thus, M is countable?

I don't feel like this proof would actually work. Can anybody point me in the right direction? Any help would be greatly appreciated!


texts: Can LP for matroid polytopes be solved using the greedy algorithm?

texts:
For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, although it's not done often in practice, the ellipsoid algorithm).
Matroids are well known for the property that the greedy algorithm is optimal if and only if it is performed for a weight function defined on the bases of a matroid. (Or something similar.)
Question: In special cases where we can somehow create a correspondence between vertices of a polytope and bases of a matroid, does the greedy algorithm provide a solution for LP?
The answer to this seems like it might be yes based on the paper The Bergman Complex of a Matroid and Phylogenetic Trees by Federico Ardila and Caroline J. Klivans. However, the exposition does not confirm or deny this suspicion explicitly, and without an explicit statement either way, combined with the fact I am not 100% certain I understand the definitions, I am still unsure if it is true or not. Below I quote the portion with the relevant definitions and hint:

Let $M$ be a matroid of rank $r$ on the ground set $[n] = \{1,2,...,n\}$, and let $\omega \in \mathbb{R}^n$. Regard $\omega$ as a weight function on $M$, so that the weight of a basis $B=\{b_1,...,b_r\}$ of $M$ is given by $$\omega_B =\omega_{b_1} + \omega_{b_2} +\cdots+\omega_{b_r} \,.$$ Let $M_{\omega}$ be the collection of bases of $M$ having minimum $\omega$-weight... we can understand $M_{\omega}$ in terms of the matroid polytope. [emphasis mine] We will use the following characterization of matroid polytopes, due to Gelfand and Serganova:
Theorem. [6, Theorem 1.11.1] Let $S$ be a collection of $r$-subsets of $[n]$. Let $P_S$ be the polytope in $\mathbb{R}^n$ with vertex set $\{e_{b_1} +\cdots+e_{b_r} |\{b_1,\dots,b_r\} \in S\}$, where $e_i$ is the $i$-th unit vector. Then $S$ is the collection of bases of a matroid if and only if every edge of $P_S$ is a translate of the vector $e_i − e_j$ for some $i, j \in [n]$.
Let $P_M$ be the matroid polytope of $M$. We can now think of $\omega$ as a linear functional in $\mathbb{R}^n$. The bases in $M_{\omega}$ correspond to the vertices of $P_M$ which minimize the linear functional $\omega$. [emphasis mine] Their convex hull is $P_{M_{\omega}}$, the face of $P_M$ where $\omega$ is minimized. It follows that the edges of $P_{M_{\omega}}$, being edges of $P_M$ also, are parallel to vectors of the form $e_i − e_j$. Therefore $M_{\omega}$ is the collection of bases of a matroid.


texts: 3-SAT where variables occur equally many times as a positive literal and as a negative literal

texts:
Let $\phi$ be a 3-CNF formula over variables $x_1,x_2,\ldots,x_n$. Every variable $x_i$, $i \in [n]$, occurs equally many times as a positive literal and as a negative literal in $\phi$.

Is it NP-complete to decide the satisfiability of such a formula? Assuming it is, I would be interested in knowing if it has a special name. Has it perhaps also been investigated somewhere?


texts: Doubt in understanding the time complexities of algorithms to recognize regular expressions

texts:
I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table.

The authors justify the table as follows:

Given a regular expression $r$ and an input string $x$, we now have two methods for determining whether $x$ is in $L(r)$. One approach is to use Thompson's Construction to construct an $NFA$  $N$ from $r$. This construction can be done in $O(|r|)$ time, where $|r|$ is the length of $r$. $N$ has at most twice as many states as $|r|$, and at most two transitions from each state, so a transition table for $N$ can be stored in $O(|r|)$ space. We can then use Algorithm 3.4 to determine whether $N$ accepts $x$ in $O(|r| \times |x|)$ time. Thus, using this approach, we can determine whether $x$ is in $L(r)$ in total time proportional to the length of $r$ times the length of $x$.

(a) A second approach is to construct a $DFA$ from the regular expression $r$ by applying Thompson's construction to $r$ and then the subset construction, Algorithm 3.2, to the resulting $NFA$.
(b) Implementing the transition function with a transition table, we can use Algorithm 3.1 to simulate the $DFA$ on input x in time proportional to the length of $x$, independent of the number of states in the $DFA$.

Dependencies:

Algorithm 3.4

Algorithm 3.2

Algorithm 3.1

Doubt: The point where I am having the doubt is that why are the authors only considering the time complexity of just the algorithm 3.1 and not the time of rest of the work done in the $2(a)$ and $2(b)$. Since the worse case space complexity of the DFA is exponential won't creation of the same involve exponential time as well?


texts: Converting nested absolute value into linear programming

texts:
I am having trouble writing the following optimization problem as a linear program (LP)

$$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$

where $a \in \mathbb Z^2$ is given. I tried adding the following constraints and replacing objective function to min $U$, but it did not work out.

$$x_{i}-a_{i}\le y_{i}$$

$$a_{i}-x_{i}\le y_{i}$$

$$y_{1}-y_{2}\le U_{}$$

$$y_{2}-y_{1}\le U_{}$$


texts:
Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player alternatively thereafter does the same to some single stack when it is his turn to play. The game proceeds until each stack has either just one penny or two—at which point continuation becomes impossible. The player who first cannot play is the loser. Show, by drawing a game tree, whether any of the players can always win.

My question is why does 4-2-1 not go to 2-2-2-1 ?


texts:
Is a computer file just a string of zeroes and ones? If so, can it start with zeroes?
I have not been able to find an answer, surprisingly.