texts:
I need to implement data strucure such as array, but with the following interface:

GetMin() - Returns the minimum from the array
IncRight(index) - Increases all values from specified index to the end of the array by 2
DecRight(index) - Decreases all values from specified index to the end of the array by 2

Assuming that the datastructure is already initialized, full of items (which are integers only) and we have already minimum found together with its index. So I "only" need to keep track the changes.

My goal is to all operations have amortized constant time complexity. The question is: Is it possible at all?

Anyway: How to implement such data structure with the best time complexity?

I know one more thing about the initial values: two adjacent values differs only by 1 (plus or minus).


texts: How does strong NP-completeness agree with encoding complexity?

texts:
I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like discrete knapsack) and can be solved polynomially in the values of those parameters (which implies exponential time in their binary encoding) are said to be weakly NP-complete. There exists no known polynomial-time computable mapping from any NP-complete problem which produces a unary encoded input to another NP problem like the knapsack problem, where the numerical parameters are polynomially bounded in the input length of the original problem. On the other hand, problems which are known to be NP-complete when restricted to the subset of instances where the numerical parameters are polynomially bounded in the input length of the original problem are called strongly NP-complete, but there isn't any known pseudopolynomial algorithm for those. Whether the classes of weakly and strongly NP-complete problems are the same is unknown and depends on the outcome of the P-NP question.
Now, my confusion stems from the chosen encoding. Weakly NP-complete problems are thought not to be NP-complete in their pseudopolynomially solvable instances. Those, however, are only polynomial because their input is provided in unary encoding, which avoids the exponential unfolding of the numerical values from binary format. So, an alternative way of defining weak and strong NP-completeness would simply depend on the existence of a polynomial algorithm when provided the input in unary encoding. But how could any problem being provided unary encoded input be NP-complete, that is, possess a Karp reduction (i.e. computable in polynomial time) from any other NP-complete problem? Since the original problem cannot be assumed to be given in unary encoding, its binary encoding has to be unfolded into unary encoding during the mapping, which would always require exponential time, wouldn't it? This holds even if we only require the numeric parameters of the problem be given in unary encoding, since we must assume the length of numbers to grow with the problem size. But then, this would imply that there cannot be any strongly NP-complete problems, and that any form of NP-completeness must be a weak one. Since the opposite is known, I clearly must've made an error in my reasoning, but I cannot spot it.


texts:
Assume the language:
$$L=\left\{w\in\{0,1\}^*\,| \text{ w has odd length and 111 right in the middle}\right\}$$

This is my attempt for constructing a grammar $G$ for this language:

$$G: S \rightarrow A111B,\, A \rightarrow 01B |10B|00B|11B,\, B  \rightarrow 01A |10A|00A|11A$$

This process adds random even strings of $\{0,1\}^*$ to both sides of $111$.

However, it must assign $\varepsilon$ to $A$ and $B$ simultaneously, for the even strings to be of equal length and for $111$ to stay in the middle of the resulting string.

How can I achieve the last step?


texts:
In chapter 2.2 of

Giacobazzi, Roberto; Ranzato, Francesco, Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements, Inf. Comput. 145, No.2, 153-190 (1998). ZBL0921.68057.

it's said:

  An  (upper) closure  operator (or simply closure) on a poset $C$ is  an  operator $\rho:C \to C$ monotone, idempotent and extensive (i.e.,
  $\forall x \in C . x \le \rho(x)$). We denote by $uco(C)$ the set of all closure operators on the poset $C$. If $C$ is a complete lattice then each closure operator $uco(C)$ is uniquely  determined  by the set  of its  fixpoints, which is its image $\rho(C)$

Where can I find a proof of the phrase in bold?


texts: Busy Beaver Instruction Generator and Computablity

texts:
Question 1

From busy beaver uncomputablity it follows that we cannot design algorithm that for every input N, generate the appropriate set of TM instructions (the bit value of every bit in every card) that run and output BB(N).
As i understand, the number of bits in the cards is growing almost linearly with N, so the uncomputablity situation is very strange. What prevent us in principle to design such algorithm from theoretical point of view?

Question 2

If we allow the instruction set itself to be part of memory, so that the bussy beaver will be able to change the instruction set while running, will we get faster growing function?

Question 3

If busy beaver is solution to optimization problem, is there anyway to know if some physical process that we are witnessed to, is a solution to same kind of optimization problem?


texts: What is the difference between min heap and max heap? is it possible to shuffle the elements during insertion time? If so then how come the complexity is  logn


texts: Optimize sequence when item costs are interdependent

texts:
I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there.

You're given a list of media items--songs, let's say--to play. You must play every song once, with no repetitions, but you get to pick the play sequence. The goal of sequencing is to maximize variety. For example, it would be undesirable to play two songs by the same artist back-to-back.

My initial thought was to treat items analogously to magnets that repel each other according to their degree of similarity. (Details below.) A simple brute-force implementation shows that this approach works well. However, it's of course computationally intractable. Not only are there $n!$ permutations to evaluate, but calculating the cost of a given permutation is $O(n^2)$, because every song exerts force on every other song.

Formally:  Given a set of $n$ items $\{T_1, T_2, ... T_n\}$, find the permutation $P$ $\{T_{p1}, T_{p2}, ... T_{pn} \}$ that minimizes cost function $C(P)$:

$$
C(P) = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{S(T_{pi}, T_{pj})D(T_{pi})D(T_{pj})}{R(T_{pi}, T_{pj})^2}
$$

where $S()$ is a measure of similarity between two items (take this as given), $D()$ is the duration (think "mass") of a given item, and $R()$ is the time-distance between item centerpoints.

Scheduling problems of this type often seem to have dynamic programming solutions, but those solutions usually rely on the incremental cost of the sequence-ending item being dependent only on the item's completion time. Here, the cost of the final item depends on the positioning of all other items in the sequence, which would seem to rule out that approach.

Possible ameliorating factors: A) Total cost is a monotonically increasing value as items are added to a sequence, so some unpromising starts can be pruned from the search if they already exceed the best-so-far result. B) For a given sequence prefix, interactions internal to the prefix need be calculated only once. C) True optimality is not necessary, although it would be helpful to have some guarantee of reasonability.

Questions: The usual. :-) Is this a known problem that has a literature behind it? What would the standard name be? Does any particular search method stick out as being especially appropriate? In particular, would simulated annealing be a good approach? Is there a better formulation of the problem that would have better tractability?

Thanks for your comments!


texts: Solving Unary Constraint Satisfaction Problem other than branch and bound

texts:
I am solving a problem of planning a meal, where I need to fulfill requests such as "create a two-dish meal that MUST have at most 2g of fat, the first dish MUST have 400kcal and SHOULD have at least 10g of protein, and the second dish MUST have 100kcal" by returning a list of dishes from a predefined list. In other words, it takes soft/hard constraints on a meal as a whole and sets of soft/hard constraint on each dish slot as an input, and outputs an assigment of dishes to dish slots.

I modelled it as a Constraint Satisfaction Problem with all dish constraints being unary constraints and meal constraints being used for accepting/rejecting a solution as well as ranking. I wrote Depth-First Branch and Bound roughly following [1] (shortly, it constructs depth-first a tree of all possible assignments and prunes branches with a dish violating its constraints) and it works pretty well.(*)

The problem is, I need another algorithm for solving that problem and - for reasons I can't change - it needs to be fully deterministic. Which is problematic, since:

the whole meal planning research focuses on using various flavours of artificial intelligence,
the few research papers that don't use AI, use onthologies and rule-based reasoning, but offer no details and constructing such is outside of my time budget and capabilites,
all other algorithms I could find for solving Constraint Satisfaction Problem focus on the ones with binary constraints.

I have tried to find such algorithm for about two weeks, but found nothing. I feel like I'm missing an obvious solution, but I can't quite put my finger on it.

(*) Of course, I plan to improve it by appriopriately integrating meal constraints into the search.

[1] Sundmark, Niclas. "Design and implementation of a constraint satisfaction algorithm for meal planning." (2005).


texts: $3$-dimensional convex hull using only a desired number of planes

texts:
I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to the convex hull problem, except that the convex hull can have an arbitrary large number of faces (limited only by $n$, the size of the input) while I am looking for a polytope with only $k$ faces (say, $k=8$).

Another way to phrase the problem:

  Given a large 3D point cloud with $n$ points and a small number $k$, find $k$ planes so that all points are in the polytope created by the union of the planes and that polytope has the smallest possible volume.

All "exact" convex hull algorithms I looked at (Gift wrapping, Graham scan, Quickhull) produce a polytope with a lot of faces and I can't see a way of reducing the number of faces after computing the convex hull (by merging adjacent faces or so until the face count is down to k or less).
From the "approximative" convex hull algorithms, I have thought of computing the discrete orientation polytope (k-DOP, see this PPT), but that would not be optimal (the volume would not be minimal) because it requires that each face has a parallel "partner face".

I would be happy to hear your thoughts on how to do this!


texts:
I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $[i,j]$) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]>A[i]<A[i+1]$).

There are 2 restrictions:

Only $O(\sqrt{n})$ additional space (rather than $O(n)$ which is used for the regular RMQ d.s. Also see here)
Only a constant number of entry readings from the original array while answering a query

I thought of a solution that uses $\log(n)\log\log(n)$ space. Which is $< \sqrt{n}$ for $n>1165$ according to wolframalpha. (as @jbapple said, $\log(n)\log\log(n)=O(\sqrt{n})$ so that's fine)

edit: i found an error in the solution: in part 3, each item needs to know which section it belongs to (or at least the closest local min to it) - that's already $O(n)$ additional space.

However, i won't delete it so maybe it can be modified to a correct solution

My solution:

Find all local minimums and save pointers to them in $O(n)$ time, $O(\log n)$ space $(<\sqrt{n}\space)$ .

Apply regular RMQ on $\log(n)$ local minimums (powers of $2$ technique - section 3.3 page 5 in this paper). This takes $n\log(n)$ space, but $n$ in my case is $\log(n)$ (number of "representatives"), so it'll cost $\log(n)\log\log(n)$ space only. This is for part 3 - see ahead.

Answering a query:

There are 3 types of queries:

Range begins just after a local minimum and ends just after the next one:

This is easily solved in $O(1)$ since it's either the leftmost or rightmost entry
Range between 2 local mins (not including):

Also easy (same method)
Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Sections of "local min to local min" can be solved in $O(1)$ using the regular RMQ we built above.
Regarding the other 2 sections, for each of them we can determine the min in $O(1)$ (must be either leftmost or rightmost item).
Finally we're left with exactly 3 numbers. Get their min in $O(1)$


texts:
So, I have two problems:

Minesweeper: given an undirected graph where some vertices have a whole number associated with them, check if there is a way to mark some of the non-numbered vertices such that the number in each numbered vertex is equal to the amount of its marked neighbours.
Dominating set: given an undirected graph and an integer $k$, check if there is a way to mark exactly $k$ vertices such that each non-marked vertex has at least one marked neighbour.

I need to construct a polynomial reduction from the second problem to the first (that is, using the solution to the first problem, construct a polynomial solution to the second).

I do understand that I will need to add some additional numbered vertices to the graph (because numbering any of the existing vertices will prevent it from being marked). I've tried to add a support vertex for all of the original ones and connect each support vertex to the same vertices, and after that brute-force my way through numbers in each support vertex. The problem is --- that's $O(n^n)$ and definitely not a polynomial.

How can I do this in polynomial time?


texts:
Given a group $G$, the sumset of two sets $A,B$ is denoted as $A+B = \{a+b:a\in A,b\in B\}$. We say $A$ injects $B$, if $A+B$ has no multiplicities, i.e. $|A+B| = |A||B|$. We let $I(B) = \max \{|A|:A \text{ injects } B\}$ . For practically, let's say $G$ is integer addition modulo $N$.

Given a set $B$, can we determine $I(B)$ in time polynomial in $N$?


texts: Big O notation: removing big O from denominator

texts:
In A First Course in the Numerical Analysis of Differential Equations (page 26) Arieh Iserles gives the following derivation:
\begin{equation}
\frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\xi^2+\frac{1}{3}\xi^3+\mathcal{O}(\xi^{4})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)}
\end{equation}
where $\xi=w-1$, $\rho(w)=w^2-w$ and $\xi\to 0$. I understand the expansion of the logarithm in the denominator, but how does the second step work? I have no idea how this big O is removed from the denominator. Can anyone explain this please?


texts: Algorithm for closest available resource

texts:
My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question.

Looking for algorithm for closest available resource.

n people P1-Pn, n taxis T1-Tn, are in a 2 dimensional coordinate system eg x,y

Determine Person Taxi pairs if each person walks to the closest taxi that will be available to them, and not taken by another person. Ties of two (or more) people to same taxi can go to the person of lower index. Ties of two (or more) taxis as closest taxi can go to taxi of lowest index.

Does this go by a common problem name? What algorithms exist?

As for what algorithms exist, I can think of 2 right off but I doubt they be considered efficient.
1. use recursion, eg find closest person taxi pair, remove both from available list, and run again.
2. enumerate (n squared) all possible P-T pairs into binary tree sorted by distance value, and then traverse binary tree starting with lowest value until each P has unique T.
3. or can someone offer better algorithms?
Thank you


texts: Konig's Theorem for Min Weight Vertex Cover?

texts:
Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover.

Wikipedia states that there is an equivalent version of the theorem for weighted graphs as well. I tried searching in a lot of places but could not find this theorem.

To be more specific, I want to know what is the equivalent version of Konig's theorem in the case of Minimum Weight Vertex Cover in Bipartite Graphs where each vertex $v \in G$ is assigned a weight $w_v$ and the task is to find a vertex cover of the minimum possible weight.

If the equivalence is just the maximum weighted matching in $G$, what are the weights of the edges in this graph? Because as far as I understand, we have only assigned weights to the vertices of the graph $G$.

Thank you for your time :)


texts: help understanding formal grammar for subtraction example

texts:
I am going through the following document trying to understand a simple grammar for a basic subtraction example (page 4).

The example states that

  Simple arithmetic expressions of arbitrary length built from the subtraction operator '-' and the numerals 0 and 1 can be described by the following grammar:

E = T "-" E | T
T = "0" | "1"

I understand T is the terminal symbols, but I am having a hard time understanding E.  What confuses me even more is when it is stated:

  Choosing the other alternative for E we might get the derivation...

E ==> "0" "-" E

How and why is an alternative to E include E?  Likewise, I am having a hard time understanding how ET derives "0" or how EET derives 1.

Could someone better explain this to me?  I would greatly appreciate it to move forward in the document.  Maybe with a few examples would be extremely helpful.


texts: Unordered data structure with fast insertion, deletion, and iteration

texts:
So, I need a data structure that would support the following operations:

Add an element to the structure and get some "handle" for that element
Retrieve an element by a handle
Remove an element by a handle
Iterate over all elements

Note that the elements are not expected to have any particular order in iteration. Preferably it should also be cache-friendly and don't use too many memory allocations. The language I have in mind is C++, if that matters.
A doubly-linked list satisfies the requirements (with a "handle" being just a pointer/iterator to a list node). However,

It uses a memory allocation per each new element, which is a bit too much
Iteration over a list is extremely cache-unfriendly (as compared to e.g. iteration over contiguous array)

Another possible implementation is to use a hand-written slab allocator over a contiguous chunk of memory, with each cell being either free of occupied. Occupied cells store the actual elements, while free cells maintain a singly-linked list of free cells by storing the index of the next cell in the list (or some predefined null value to mark the end of the list). A "handle" in this case would be an index of a cell. Coupled with some extra per-cell data to decide whether a cell is free or occupied, and an index of the head of the list of free cells, this structure allows

Fast amortized insertion: put the new element to the head of the list of free cells, updating the head index (and reallocating the cells array if no free cell is available)
Fast element access (just an index into array)
Fast removal: add the element's cell to the list of free cells
Fast iteration: iterate over an array, checking if the current cell is occupied

However, I am not entirely happy with this solution, since

It has to explicitly maintain the cells state (free/occupied) - this is mostly a technical inconvenience and not a serious issue
Iteration is still not branch-predictor-friendly (due to checking whether the cell is free or occupied) and might waste a lot of time skipping free cells (thanks to Andrej Bauer for pointing this explicitly), so it is an improvement only if the number of free cells is sufficiently low.

Yet another solution is to implement any kind of binary key-value tree stored inside a contiguous array (auto-expanding, like std::vector), with array indices used instead of tree node pointers, and keys serving as handles for element access/removal (their only purpose being implementing handles). This way we have

Amortized $O(\log n)$ insertion - append a tree node to the end of the array, altering the tree structure accordingly (or even $O(1)$ if the tree supports $O(1)$ insertion to the end, like a splay tree, - the data structure generates keys itself, so it can guarantee that they only increase for new elements)
Amortized $O(\log n)$ removal - remove the node from the tree structure, then swap it with the last node in the array (fixing the indices stored in the last node's children and parent), and decrement the array size
$O(\log n)$ element access via the tree structure on keys
Ideal iteration: simply iterate over the whole array (even better if we keep values in a separate array, synchronized with the array for the tree structure, since the latter is not needed for iteration)

This solution trades iteration speed for $O(\log n)$ other operations.
I am mostly interested in increasing the iteration performance, while still retaining fast amortized insertion/deletion. I'm ok with spending some extra $O(n)$ memory, shall the need arise.
So, here's my question: are there better options for a data structure with these requirements?


texts: What should I read to understand semantics of programming languages?

texts:
I would like to have a good conceptual understanding of the semantics of programming languages: operational-, denotational-, axiomatic-, categorical-.

Is there a good (standard?) textbook for this?


texts: Creating a top-hat distributed random number generator

texts:
I have this Fortran code which generates a flat distribution as it produces a single random number centered on 0.
The function GRNDM (Geant 4 random number generator) produces equally distributed random numbers between the values of 0 and 1. RDUMMY is the name of the vector filled with the random number and the argument "1" states the length of the vector: i.e. GRNDM here will produce a single random number between 0 and 1. The second line then produces random numbers in the interval [μ−σ2,μ+σ2].

I was wondering if there was a way of changing it to produce random numbers with a top hat distribution?


texts: Can you use a Bayes classifier to determine if something is NOT in a defined class?

texts: I know I can use a Bayes classifier to determine if something is one of N classes, but can I also determine if something is NOT in any of the predefined classes?  Or will a Bayes classifier only find the closest class?


texts: I've always wondered why processors stopped at 32 registers. It's by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn't that mean less going to the RAM?


texts: Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

texts:
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?

Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for some $k$ satisfying the property that $(u,v) \in E$ implies $\chi(u)\ne\chi(v)$ so as to minimize the fewest number $k$ of “colors”.


texts: Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

texts:
Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to prove it.

My thoughts

This "50 steps" part immediate turns the R sign for me. If it was for specific input it would be decidable. However, here it's for every input. Checking it for infinite inputs makes me think that the problem is co-RE, i.e. its complement is acceptable.

Perhaps, I can check the configurations and see that all configurations after 50 steps don't lead to accept state- how do I do that?


texts: Show that the inequality holds for all positive integers

texts:
$a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$ for $n>=3$
Show $a_n<3^n$ for all positive integers n
Base case: $a_3 = 2*9+3*2 = 24<=3^3$ is true
Hypothesis: $a_k<=3^k$ for $k\epsilon\mathbb{N}$, show $a_{k+1}<=3^{k+1}$
Begin:
$a_k<=3^k$ implies $3a_k<=3^{k+1}$
by definition: $a_{k+1} = 2a_k+3a_{k-1}$
$2a_k + 3a_{k-1} <= 2a_k + a_k = 3a_k <= 3^{k+1}$
Because $3a_{k-1} = 2a_{k-1} + a_{k-1} = 2a_{k-1}+2a_{k-2}+3a_{k-3}$
$3a_{k-1}$ will always be smaller than $a_k$ because $2a_{k-2}+3a_{k-3}$ is always smaller than $3a_{k-2}$
So because $a_{k+1} <= 3a_k$ and $3a_k<=3^{k+1}$ then $a_{k+1}<=3^{k+1}$ which proves $a_n<=3^n$ for all n
Is my proof legit?


texts: Call by value-result vs. call by reference?

texts:
From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee exits, and that if the same variable is passed as more than one argument, it'll be treated as separate values in the callee instead of the same value as in call by reference.

Neither fact helps me explain why call by value-result produces different output than call by reference in the following code:

program Param (input, output);
var
  a, b: integer;
  procedure p (x, y : integer);
  begin
    x := x + 2 ;
    a := x * y ; (1)
    x := x + 1   (2)
  end;
begin
  a := 1 ;
  b := 2 ;
  p (a, b) ;
  writeln (a)
end.

Edit: here's my understanding of things:
The insight here is that in CBR, in line (1), both a and x point to the same thing, so assigning to a updates both a and x to x * y which is 6. But in CBVR, a and x point to different things, so line 1 only updates a to 6. x remains 3. Then CBR updates a right away so a ends up being 7 outside p. But CBVR updates a to whatever x is at the end of p, which is 4, so even though a was 6 in line (1), after p exits it's changed to 4.


texts:
What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String number representation while considering their range, endianess and layout, sign and JVM specifics? The algorithm used for say byte may differ from int due to the range. char would be a special case.
ryu gives floating-point to String conversions but not for the other primitive types.
There are some C/C++ solutions but I could not find any Java specific ones:

https://www.zverovich.net/2020/06/13/fast-int-to-string-revisited.html
https://johnnylee-sde.github.io/Fast-unsigned-integer-to-string/
https://github.com/miloyip/itoa-benchmark


texts: Why does $2^{O(\log n)} = n^{O(1)}$ hold?

texts:
I was recently looking at the article on the P complexity class on Wikipedia. In the section on relationships to other classes, it mentions that P is known to be at least as large as L, giving this explanation:

  A decider using $O(\log n)$ space cannot use more than $2^{O(\log n)} = n^{O(1)}$ time.

The article sadly fails to explain how that last equality holds. How exactly does one go about showing that $2^{O(\log n)} = n^{O(1)}$?


texts:
I am trying to understand different interactive proof systems, in particular AM and MA.

Is there a typical problem for the complexity class MA
as Graph-NonIsomorphism problem is for AM?

Is there a problem in MA that is not known to be in NP or BPP?

It seems to me that MA is a more natural proof system than AM.
Is there a reason that most books discuss AM in detail
while merely glossing over MA?


texts:
In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about:

FACT

Given: A composite number, i.e. a positiv integer which is the product of some prime numbers: $x = p_1 \cdot p_2 \cdot \ldots \cdot p_n$  You know only $x$.

Wanted (calculation problem): At least one factor of this composite number.

As a decision problem: For a given $k \le x$: Is there a factor $p_i \le k$?
(You just need to solve the decision problem $\log x$ times to solve the calculation problem. So, as long as the complexity of the decision problem is polynomial or harder, both flavors of the problem belong to the same time-class.)
DISCRETE LOG

Given: $x = a^n \mod p$. There $p$ is prime and you know $x$, $a$ and $p$.

Wanted (calculation problem): Find $n$.

As a decision problem: Is there some $n \le k$ such that $x=a^n \mod p$?
(Also here you need to solve the decision problem only $\log p$ times to solve the calculation problem.)

I know, that both problems, as far as we know, are not in the complexity class $P$, i.e. for both problems there is no algorithm know that could solve them in polynomial time on a deterministic Turing Machine.

I know, that both problems can be solved in polynomial time on a non-deterministic Turing machine, which, per definition means, that both of them are in the class $NP$.

Let's suppose, that $P \ne NP$. Under this assumption $NP$ is partitioned into three sub-classes:

$P$
All problems which are solvable in polynomial time on a deterministic Turing Machine
$NPC$
NP-complete.
The subset of $NP$ to which all problems in $NP$ can be reduced, i.e. the subset of $NP$ that is NP-hard.
$NPI$
NP-intermediate
All problems which are in $NP$ but neither in $P$ nor in $NPC$.

It is known, than $NPI$ is not empty if $P \ne NP$ (Ladner's theorem).

(If $N=NP$, then also $NPC=P$, which means, that $NPI$ must be empty.)

I know, that under the assumption that $P \ne NP$, FACT seems to be in $NPI$, since until now nobody could prove that FACT $\in NPC$.

But I could not find similar statements about DISCRETE LOG.

Here are my questions:

Is DISCRETE LOG know to be in $NPC$? Or is it thought to be in $NPI$?
If it is in $NPI$:

Is there a know algorithm to reduce FACT to DISCRETE LOG?
Or is there an algorithm to reduce DISCRETE LOG to FACT?
Are they maybe even equivalent, i.e. reduzibel in both directions?


texts: Why is the probability used in the definition of RP complexity classes, arbitrary?

texts:
I was looking at the following wikipedia article on the RP complexity class:

https://en.wikipedia.org/wiki/RP_(complexity)

In its definition it states:

If the correct answer is NO then it always returns NO
If the correct answer is YES then it returns YES with a probability of 1/2

At the end of the introduction it says:

  The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.

What I don't understand is why this 1/2 is arbitrary? If you change it to 1/3 does it really still contain the same set of decision problems as with 1/2?


texts: Better version of heavy-light decomposition: always draw path to largest subtree

texts:
Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ).
The problem: given any tree of size N, find a way to split it into some disjoint paths such that from any node, you can reach the root by passing through log N paths. Heavy light decomposition: https://cp-algorithms.com/graph/hld.html
I was thinking that a small modification is that instead of choosing an edge only when a child's subtree is of size at least half of this subtree, you just choose the largest subtree. Proof that this works is the same: when you switch paths, the size of the subtree must at least double.
Edit: just noticed that the link also mentions you can do this, so I'm wondering why heavy-light decomposition is used instead of this, because this seems easier to understand and also slightly more performant (because of less paths).


texts: how to find the depth of a concurrency bug

texts:
How to find the depth of a concurrency bug

The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug in it.

Bug: Any time both threads perform a read before they write we loose an update to x.

Thread 1

 1. t1=x
 2. t1=t1+1
 3. x=t1

Thread 2

 1. t2=x
 2. t2=t2+1
 3. x=t2

I am told the depth of the bug is 2. My question is what is the process to find the depth of a concurrency bug?


texts:
I have a list and want to select a random item from the list.
An algorithm which is said to be random:

When you see the first item in the list, you set it as the selected item.
When you see the second item, you pick a random integer in the range [1,2]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.
For each item you see, you increase the count, and with probability 1/count, you select it. So at the 101st item, you pick a random integer in the range [1,101]. If it's 100, that item is the new selected node.

Is it really uniformly random?
My thoughts are:
As the number of nodes increases, the probability for them being selected
decreases, so the best chance of selection is for items 1, 2, 3, ..., not for 20, 21, ..., 101.
Each node will not have equal probability of being selected.
Please clarify, as I have trouble understanding this.


texts: Feedback polynomial of 7-bit Linear Feedback Shift Register


texts:
I have some questions that I don't understand about time complexity.

Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case
complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
Given that the best case complexity of the algorithm $A$ is $O(f(n))$ and the worst case
complexity of $A$ is $Ω(g(n))$. It follows that $f(n) ∈ Ω(g(n))$.
Given that the average case complexity of the algorithm $A$ is $Θ(f(n))$ and the worst
case complexity of A is $O(g(n))$. It follows that $f(n) ∈ O(g(n))$.

I will appreciate if you can help me understand those!
Thanks a lot!


texts: Complex search algorithm - Points on a sphere - Best approach

texts:
I have a very complex search problem which I can't wrap my head around:

  While reading please remember I'm not asking for a specific solution! Only a general approach how such a problem can be solved and what kinds of algorithms to use (more below)

I have a sphere with around 120 000 weighted and named points mapped on its surface.

Now I take a section out of the sphere with somewhat around 10 of the highest weights (not guaranteed the 10 hightest weights!)

The Problem: I want to find the spot where the section was taken out, so that i could assign each point the "name" it would have had on the sphere

Characteristics of the points on the sphere.:

120 000
The coordinates are exact
The points are weighted

Characteristics of the points in the sector:

The points are also weighted. The proportions are roughly the same as on the sphere, unfortunately I don't know a single inital weight. So my only chance is to compare the proportions.
Not every point which is on the sphere is also visible in the section (sometimes only 5-10%). However the weigths matter:

The hightest weighted points do always appear.
The first non-visible points have guaranteed less weight than most of the visible points.

The section could be rotated
All points are a bit offset (not by much), but they aren't exactly on the spot where they were on the sphere
Other errors could be possible too (like counting 2 points only once)

Additional info which might make the problem simpler:

The sector is only around 1°x1° to 5°x5°. So maybe i could use a flat map instead of a sphere. (Just like Google Maps if you zoom out enougth
The first non-visible points have guaranteed less weight than most of the visible points.

What I'm asking for:

  What is the general approach to solve this problem? Are there any algorithms you might now on which I can orientate myself?

  Anything between pure brute-force and AI is welcome!

Example image of a sector region which is detected by my algorithm:
(A larger red rectangle = higher weight)

If you think this is a good question please consider upvoting to draw attention.


texts: How many bits representation of data on tape of Turing machine consumes

texts:
I am wondering how to represent signed number, vector, matrix on binary tape of Turing machine to consume the smallest possible amount of memory.

For signed number it is obvious: encode sign as a single bit and sum it with the length of number representation $\lceil\log_2(\mathrm{abs}\,(n)+1))\rceil$.

But how is it possible to represent a vector of numbers with different size. How to consume minimal amount of memory?


texts: Maximizing sum of ranges of vertices edges

texts:
Consider an arbitrary undirected graph $G = (V,E)$.  Suppose you have a collection of $|E|$ positive integers and each integer must be assigned to one edge.  Let us denote the collection of integers assigned to vertex $v$'s edges as $w(v)$. How would one assign the $|E|$ integers to the $|E|$ edges so as to maximize:

\begin{equation}
\sum_{v \in V}{max(w(v)) - min(w(v))}
\end{equation}

In other words, how would one maximize the sum of the range of each vertice's edge assignments?

As an example, consider the graph pictured below.  Same graph, same set of $|E|$ integers, but different assignments of integers to edges leads to the above equation evaluating to either 16 or 18.


texts: Proving that f(N) = N lg N + O(N) implies f(N) = Θ(NlogN)

texts:
How do you prove the following?

$$f(N)=N\space lg\space N + O(N) \implies f(N) = \Theta(N \space log \space N)$$

Here $lg\space N \equiv log_2\space N$, and $O$ stands for the big-O, and $\Theta$ stands for big-theta. And $log \space N \equiv log_e \space N$, i.e. natural logarithm

My reasoning may not be all that mathematically pleasing (or even correct)...but here goes...

  We have $f(N)=N\space lg\space N + O(N)$

  By definition, $O(f(N))$ stands for the some upper bound for the
  function $f(N)$.

  Therefore, in our relation $O(N)$ (being an upper bound function)
  should theoretically contain $f(N)$ as $N \rightarrow \infty$.

  Now consider the lower bound of $f(N)$ to be some function of $N \space lg \space N$, i.e. $\Omega(f(N)) \equiv f(N \space lg \space N)$

  Now, $lg \space N \equiv log_2 \space N > log \space N$, where $log$
  stands for natural logarithm. Hence natural logarithm is some constant factor of "binary" logarithm, where that constant is less than 1.

So all the above reasoning naturally implies our above assertion, right? Where am I wrong?


texts:
(Re-posted from StackOverflow as suggested)

I have the following problem.

The functions $f(x),g(x)$ are defined as
$$
f(x) = \begin{cases} f_1(x) & 0 \leq x \leq 10, \\ f_2(x) & 10 < x \leq 20, \\ 0 & \text{otherwise}, \end{cases} \qquad
g(x) = \begin{cases} g_1(x) & 0 \leq x \leq 5, \\ g_2(x) & 5 < x \leq 20, \\ 0 & \text{otherwise}, \end{cases}
$$
In addition, we require the constraints
$$
\int_0^{20} f(x) dx \geq K, \quad \int_0^{20} g(x) dx \geq Q, \quad f(x)+g(x) \leq R \text{ for all $x$}.
$$
where $K,Q,R$ are parameters.

I assume there is quite some elaborate theory behind it, and was wondering if anybody could point me in the right direction to devise an algorithm that can generate $f_1(x), f_2(x), g_1(x), g_2(x)$?

I would like to add that for a given $K$ and $Q$, the interest is to keep $R$ as low as possible.


texts: Is modulus capable of universal computation?

texts:
I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers?

It was a long while ago though and don't remember where I heard it.

Is this true or does it ring any bells?


texts: Probability of a document is not the same as 1/number of documents, is it?

texts:
Currently, I am writing code in Python for a paper that I'm reading and has been implemented in R already by the author.
For this paper we have a corpus with $n$ documents and $m$ words.
In one of the steps, I have to calculate the probability of document $j$ as follows:

Step 4 We use document-term matrices with the GTW methods in step 2 (Words ⨉ Documents matrix) to find $\mathbf{P(D_j)}$ or probability of document $j$: $$ P(D_j) = \frac{\sum_{i=1}^m (W_i,D_j)}{\sum_{i=1}^m \sum_{j=1}^n (W_i,D_j)} $$

Here:

$W_i$ = word $i$
$D_j$ = document $j$

I interpret this as computing  a vector of length $n$ in which each cell is the sum of GTW values of all words $W_i$ within one document $D_j$, divided by the total sum in all the documents.
However, in the R code, $P(D_j)$ is calculated as a vector of length $n$ where each cell has the value 1/number of documents. Based on my interpretation, this implementation does not align with the formula.
Am I interpreting the formula correctly?


texts: Numerical issues in solving linear systems

texts:
There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows:

Consider the linear system
$$ \begin{bmatrix} a & b \\ b & a \end{bmatrix} \times \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$
with $a,b>0$.
a) If $a$ is very similar to $b$, what is the numerical difficulty in solving this linear system?
b) Suggest a numerically stable formula for computing $z = x + y$ given $a$ and $b$.

This is a Computer Engineering course, however I am not able to answer these questions. What is the keyword to find a solution on the issue?
Thanks in advance.


texts:
I'm new to formal language and automata theory and I was left alone with this exercise. The task is to define a formal grammar for given language.

$Σ \in \{a,b\}$

$L = \{ w \in Σ^*\, |\, |w| \equiv 2 \mod 3 \} $

I already solved tasks of that kind, but now i struggle to understand what $|w| \equiv 2 \mod 3$ means. $|w|$ means the length of $w$ right? Does $\equiv 2 \mod 3$ mean that $|w|$ should be $2$ (because 2 modulo 3 is 2)?


texts: How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$

texts: I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a recursive formula where d = 1 + min(dL, dR) where dL and dR are the depths of the left and right subtree of the root. But can't get a solution of this. Can anyone help me out here?


texts: Algorithm to convert many instances of unidirectional lists to a graph?

texts:
I feel like I'm missing something basic.
I have instances of a list compromising of unique graph nodes / elements visited. Lists happen in order, but follow graph based rules (can be cyclical, only some connections are allowed, there are optional nodes in a graph, some nodes always happen in unison, etc). How can I derive the graph represented by billions of instances of these lists? And maybe even sub-graphs nested within?
e.g. list instance #1: A -> B -> D -> E
e.g. list instance #2: A -> F -> K
e.g. list instance #3: A-> B-> K > B -> D -> E

e.g. graph vertices derived from these lists:
A -> B
B -> D
B -> K
D -> E
F -> K

This feels like a solved compsci problem that I'm trying rearticulate. Like, I get that I can always calculate the vertices (either by weight / likelihood to occur, or as booleans if they occurred). But that feels like I'm missing a lot of nested complexity and trying to reinvent the wheel. Is there an esteblished approach to this problem?


texts: Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

texts:
Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$.

Is answering to that problem yes or no equivalent to subset-sum problem?
What would be the complexity of finding such path?

I have made a reduction from subset-sum problem:

If each number in a set $S$ is a vertex of $G$ and weight of $<i,j>$ is $|i-j|$, then answering the question above yes or no is the same as solving the sumbet-sum problem.

P.S. The initial vertex I have visited is added to the cost.

Edit: Edge weights


texts:
In the examples I was given I have the following NFA diagram:

Then it gives the conversion process

Could someone explain to me the process of obtaining the second column:

{1,2,4} = a{1, 2, 3, 4}, b{1, 4, 5}


texts: exact matching between two strings - linear edit distance?

texts:
This is the problem, given a string with characters from: a-z, ., *, and another string with characters from a-z. where * can delete the character before it, otherwise * is skipped and . can match any single character. the question is whether the first string can match the second one.

Note: That is the statement of the problem as I found, but in this case the character * performs the same function that ? in a regular expression.

Example:

isMatch("a*", "") = true; //"a*" could be "a" or an empty string ""
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;

I've already solved this problem using a slightly modified edit distance, which I only know a 2D dynamic programming approach. I wonder whether exists a linear solution for this problem, maybe it is solvable without a dp approach?


texts: Enumerate all combinations of operations that fit memory and time criteria

texts:
I have the following problem:

$x$ is the number of operations I have to perform.

$O=\{o_1,o_2,\ldots o_n\}$ is the set of possible operations.

I know beforehand the cost in terms of time and memory of every operation $o_i \in O$.

I have a limited amount of memory and computation time, $M$ and $T$ respectively.

What is the most efficient way to generate the list of computable combinations? i.e. I need to generate a set of computables $C=\{c_1,c_2,\ldots c_m\}$ such as:

$\forall c_i \in C, c_i$ is a combination (with possible repetition) of $O$ and $|c|=x$
$\forall c_i \in C$ the memory and time consumption should be less than $M$ and $T$ respectively.

I think this is an operations research problem, but I can be wrong. If so, what branch of operations research? If not, then what is the most suitable approach?


texts: Counting the number of satisfied models - given mathematical constraints

texts:
Question
There are plenty of algorithms for solving the #SAT problem, with one being the DPLL algorithm and is implemented for all kinds of programming languages. As far as I've seen, they all take a boolean formula on CNF as input and outputs the number of satisfied interpretations.
Mathematical constraints, on the other hand, is another way defining an instance of SAT-problem and is often used in discrete optimization, where one tries to optimize some function with respect to these constraints. Is there a program taking mathematical constraints as input and outputs the number of satisfied interpretations?
Example
We represent the boolean formula $Q = (a \lor b) \wedge (c \lor d)$ as constraints as $$a + b \geq 1 \\ c + d \geq 1$$ or as a matrix $A$ and support vector $b$
$$
A=
\begin{bmatrix}
    1 & 1 & 0 & 0 \\
    0 & 0 & 1 & 1
  \end{bmatrix} \\
b = \begin{bmatrix} 1 & 1 \end{bmatrix}
$$
where all variables $a,b,c,d \in \{0,1\}$. We know there are programs taking $Q$ as input and outputs the number of interpretations but are there programs taking $A$ and $b$ as input (or similar construction) and outputs the same number of interpretations?


texts: Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

texts:
I have created the following solution but its left recursive:
S--> a|bSc|cSb|Sbc
Also it is not accepting:
"ab" or "cba" or "abb" or abc.

Somebody please guide me.

Zulfi.


texts:
Problem: Given a graph G with positive integral weights on nodes as well as edges, find an induced subgraph H with maximum total weight per node, i.e., the goal is to maximize
$$
\frac{ \sum_{e \in H}w(e) + \sum_{v \in H} w(v) }{|V(H)|}.$$
If you allow negative weights, then it is NP-hard (easy reduction from Clique). I have a strong feeling that the above is not NP-Hard.
I would love to have some first-thoughts on the above, if not a full-fledged optimal algorithm. Does it seem to be NP-Hard? What is the closest known problem -- my thoughts were Prize Collection, Clique -- but both seem much harder.


texts: Can you create a deterministic PDA for non-palindomes?

texts:
Using non-determinism to create a PDA to recognize non-palindromes is easy.

My first instinct was to say yes, but it would be extremely complicated. After thinking about it, I don't think you could.


texts:
There are two classes of binary functions, $F_1,F_2$. The VC-dimension of $F_i$ is $d_i$. Is there any simple formula for the VC-dimension of the following classes?

$F_\lor := \{ f_1(x) \lor f_2(x)  | f_1\in F_1 \text{ and } f_2\in F_2\} $
$F_\land := \{ f_1(x) \land f_2(x)  | f_1\in F_1 \text{ and } f_2\in F_2\} $


texts: How can a device decipher spoken English words?

texts: I want to know how it can process spoken English words and Pull out a matching response? Is it a chip or a installed software? Does it take up a lot of space? Thanks.


texts: Can there exist a smaller NFA then a minimal DFA

texts:
So every NFA can be transformed to a DFA and every DFA can be transformed to a minimal DFA.

But every NFA can also be transformed to a GNFA (generalized NFA) with 2 states. This is just the start and end-state with the RE of the $ L_{NFA} $ written on the bow between.

So I think  the GNFA can be smaller (less states) because you can make choices. For instance a bow from state 1 to state 2 could contain: $ ab | a $ which in a DFA would require more states.

So my question is basically: Am I right about this? Can you there exist a smaller NFA to a minimal DFA?


texts: Algorithm to maximize $j-i$ subject to $A[j]>A[i]$

texts:
We want an algorithm that, given an array $A$ of length $n$ of integers (indexed by $A[0],A[1],\ldots,A[n-1]$, determine values $i<j$ that maximizes $j-i $ subject to $A[j]>A[i]$ (if such values $i,j$ exist.)

One possibility is as follows: First check whether the array is non-increasing. If so, no such $i,j$ exist. Else, iterate through the elements from front to back, keeping a running array which we append the current element if it is the minimum so far. This running array is decreasing, and we can use binary search to find the greatest element that's less than the current element. We update $j-i$ if it beats the previous maximum. This takes time $O(n\log n)$ because of binary search.

Is there a faster way, e.g., an $O(n)$ algorithm?


texts:
Consider the following statement

  In FOL, we can reduce entailment checking to satisfiability checking:

  $S \models  S' \iff S  \land \neg S'$ is satisfiable (This proof
  strategy is called refutation).

Is the above statement true? If yes, then I got confusion because of the following steps

$ S \models  S' \iff S\implies S'$ is true

$S \models S' \iff \neg S \lor S'$ is satisfiable

$S \models S' \iff \neg( S \land \neg S') $ is satisfiable

$S \models S' \iff  S \land \neg S' $ is unsatisfiable

Which one is true?


texts: modelling communication costs on a network

texts:
Consider a set of $N$ computers. Each computer needs to send some data to $K$ other computers, and each computer is receiving data from $K$ other computers (ie. the communication pattern can be thought of as a K-regular graph -- this can be relaxed, if needed). One can assume that the amount of data sent between two computers is always the same, if that makes things more simple.
I am trying to model as simply as possible the time it would take for all the data to be transferred. The computers could represent processing units within the same data center, for example, or within a same computing cluster (eg. communicating with some kind of MPI). To fix the notations, call $\tau$ the time it would take if there were only two computers $A$ and $B$, and $A$ were sending data to $B$.
A few models:

if one assumes that there is a single bottleneck through which all the data has to go through, it would roughly take $T \approx N \times \tau \times K$.
if everything can be done in parallel, this could take about $T \approx \tau \times K$, or maybe even $\mathcal{O}(\tau)$, but this seems quite unrealistic. This would for example be the case, I think, if the computers were spread out very far from each other on the Internet, say.

Any idea how this should be modelled? Any reference?


texts: Why do more powerful programming languages tend to have slower implementations?

texts:
I was reading this article. The author talks about "The Blub Paradox". He says programming languages vary in power. That makes sense to me. For example, Python is more powerful than C/C++. But its performance is not as good as that of C/C++.
Is it always true that more powerful languages must necessarily have lesser possible performance when compared to less powerful languages? Is there a law/theory for this?


texts:
Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the language generated by a grammar.

Apart  from practical considerations, such as implementation difficulty and orderliness of derivations, is there any other reason why we usually do not discuss about arbitrary derivations (not rightmost or leftmost)?


texts: Matrix Inversion in the complexity class $P$ seen as a decision problem

texts:
If the set $P$ is defined as the set of decision problems that can be solved by a deterministic Turing Machine in polynomial time, and matrix inversion using Gaussian elimination is $O (n^3)$, then how can I relate these two concepts to conclude that inverting a matrix is in $P$?

I suppose I need a way of converting a description of Gaussian elimination into a decision problem? Or maybe I am confused about the fundamentals


texts: Using chebyshev polynomials to calculate LOG, EXP and TRIG functions

texts:
I originally posted this over on Software Engineering, but it was suggested that I repost it here.
I am working on a BCD Floating point library and I'm a bit stuck on the EXP (antilog) functions.  The goal is to maintain accuracy for the entire length of the number which could exceed 100 significant digits.
So the requirements are fast and accurate to N digits.
I have been experimenting with the Taylor series and found that it will yield an answer, but requires about 2 iterations per digit.  It takes two multiplies and one divide per iteration. Plus I am not satisfied that it is all that accurate because it seems to converge on the correct answer only to drift away.
I would like to know if this can be done with chebyshev polynomials to converge on the correct answer in fewer iterations and clock cycles.  I do have a chebyshev example, but it is limited to 8 iterations and about 9 digits of accuracy.  I found no explanation as to how to expand it for more significant digits.
Does anybody have a chebyshev, or better, algorithm that can calculate EXP (any base)?  Please no complicated math proofs as they are likely over my head.


texts: A problem with the greedy approach to finding a maximal matching

texts:
Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\{(a,b), (b,c), (c,d)\}$. Then I have seen the following proposed as a greedy algorithm to find a maximal matching here (page 2, middle of the page)

Maximal Matching (G, V, E):
M = []
While (no more edges can be added)
     Select an edge which does not have any vertex in common with edges in M
     M.append(e)
end while
return M

It seems that this algorithm is entirely dependent on the order chosen for which edge is chosen first. For instance in my example if you choose edge $(b,c)$ first, then the you will have a matching that consists only of $(b,c)$.

Whereas if you choose $(a,b)$ as your starting edge, then the next edge chosen will be $(c,d)$ and you have a matching of cardinality 2.

Am I missing something, as this seems wrong? I have also seen this described as an algorithm for finding a maximal matching in the context of proving that the vertex cover approximation algorithm selects a vertex cover by choosing edges according to a maximal matching. Any insights appreciated.


texts:
I know that for most computation involve nan (not a number) the result is a nan itself except for some cases.
For example, $1^{\text{nan}} = 1.00$ which proven by mathematicians to be true.
I tried to find a proof but failed
so my question is how to prove that $1^{\text{nan}} = 1.00$?


texts: Mistake in a proof of termination phase of Simplex algorithm in CLRS?

texts:
There is a pseudo-code for Simplex algorithm in CLRS:

The proof consists from three-part loop invariant:

Proof We use the following three-part loop invariant:
At the start of each iteration of the while loop of lines 3–12,

the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,
foreach $i \in B$, we have $b_i$ >= 0, and
the basic solution associated with the slack form is feasible.

The initialisation and maintenance phases are clear for me.
But, the termination case seems(not sure) wrong to me:

So, my question is:
It is unclear for me that $\bar{x_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x_e \leq 0$. What am I missing ?


texts: Having trouble proving vertex cover greedy algorithm

texts:
So this is my first time posting, but I don't know where else to go. I've spoken with several PHD and Masters students and they referred me here. I've been looking at the Vertex Cover problem and came up with an algorithm to find the optimal minimum. I've tried this on several graphs as examples and it's found the optimal every time. Could someone please help me prove that either this finds the optimal for all VC problems or if there is a counter example disproving it? Thanks in advance.

Given Graph G = (V,E), find minimum Vertex Cover

Sort the vertices by the number of edges associated; greatest to smallest O(nlogn)
While there are unmarked edges in E: O(V)

Select the vertices with the highest edge count (total), put vertex in set S, and mark it’s associated edges O(V*E)
Break ties by prioritizing the vertices with the fewest marked edges. If a tie still exists, handle arbitrarily.
Skip vertices that have no unmarked edges.

For each vertex in S, in the order they were added:

Remove vertex from set S and update edge markings. If any associated edge becomes unmarked, reselect vertex and remark the edges. Otherwise, remove vertex from S (nobody wanted them anyways ) O(V*E)

Return S

Algorithm runs in O(V*E). The edge markings can be maintained in a VxV table.


texts:
In the book here: http://neuralnetworksanddeeplearning.com/chap3.html

If you scroll down to Exercise 2 in the Softmax Section, it says

  Show that $\partial a^L_{j}/\partial z^L_{k}$ is positive if $j=k$ and negative if $j \neq k$. As a consequence, increasing $z^L_j$ is guaranteed to increase the corresponding output activation, $a^L_j$, and will decrease all the other output activations.

Here,
$$a_j = \frac{e^{z^L_{j}}}{\sum_{k}{e^{z^L_{k}}}}$$

I managed to prove the part when $j \neq k$ by differentiating as normal to get
$$-\frac{e^{z^L_{j}}}{\left(\sum_{k}{e^{z^L_{k}}}\right)^2}$$

which is obviously always negative. However I'm having trouble with when $j=k$.
When I differentiated I got an inequality which simplified to proving
$$\sum_{k}{e^{z^L_k}}>1$$
I am unsure of how to do this.


texts:
I have seen a proof that $E_{LBA}$ is not decidable. But is it  at least turing recognizable? How to prove it?

NOTE: $E_{LBA}$ is defined as the emptiness problem for Linear bounded automaton


texts: What is a graceful algorithm to generate this number sequence

texts:
0                   0
1                   1
1 0                 2
1 0 0               4
1 0  1              5
1 0 0 0             8
1 0 0 1             9
1 0 1 1             11
1 0 0 0 0           16
1 0 0 0 1           17
1 0 0 1 1           19
1 0 1 0 1           21
1 0 1 1 1           23
1 0 0 0 0 0         32
1 0 0 0 0 1         33
1 0 0 0 1 1         35
1 0 0 1 0 1         37
1 0 0 1 1 1         39
1 0 1 0 0 0         40
1 0 1 1 1 0         46

So the idea of this sequence is based on patterns in the binary.
Namely we don't ever repeat patterns. So if you have 1 0, you will never include 1 0 1 0 or 1 0 1 0 1 0
And you also throw out all rotations of a binary sequence within a given digit length. If you have 1 1 0 0 you will never have 1 0 0 1

What is a minimalistic algorithm for generating this sequence and does this sequence have a name?  My interest in this sequence is musical as this is a concise list of rhythms in order of complexity.


texts: how to use the solution of mean payoff game to arrive at winning regions of parity game?

texts:
The 7th chapter (7.3 section) of "Automata Logics and Infinite Games" by Erich Gradel, Wolfgang Thomas, Thomas Wilke gives a way to convert max parity game to mean payoff game.

I do not understand how to use the solution for mean payoff game i.e $\nu(v)$ to compute the winning region of parity game.

It states "It is our goal to find the values at the vertices efficiently. This immediately gives us the winning region." But there is no further explanation.

Is the winning region those set of vertices for which $\nu(v) \geq 0$ ?

Conversion from parity game to mean payoff game :
Suppose our parity game is (A, Ω). W.l.o.g. the priorities are {0, . . . , d − 1}. The mean payoff game uses the same arena. An edge originating at a vertex v with priority i = Ω(v) receives the weight $w(v, u) = (−1)^in^i$. Let ν = 0. Clearly all weights lie in the range $\{−n^{d−1}, . . . , n^{d−1}\}$. This defines our mean payoff game (A, 0, $n^d$, w).


texts: What are the asymptotic bounds (upper bound on time complexity) of the following function?

texts:
I am trying to find the upper bound on time complexity of the recursive function defined by the following equation:
$$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\frac{m-1}{m}}\quad \forall\, t = 1, \ldots,T-1.$$
Here, $0\leq q_i\leq 1$ are probabilities where $\sum^{N}_{i=1}q_i = 1$. Also, $g_i$ and $Q(t)$ are real valued numbers ($Q(T)=0$).
I should mention that Im interested in complexity with respect to $N$ and $T$ (since I find complexity analysis with respect to $m$ very hard). From my understanding the term inside the summation, i.e., $$q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\frac{m-1}{m}}$$ can be considered as a constant time complexity operation since it does not depend on $T$ or $N$. Since, the term inside the summation is calculated $N$ times and for $t = 1, \ldots, T-1$, then the time complexity is $O(NT)$

I need help in verifying this.


texts: Measure of network branchiness on a weighted graph

texts:
I'm working with road networks, in which each edge is a physical street segment with a length attribute. Nodes represent junctions.  However, my question should be generalizable to any weighted graph.

I'm interested in a specific measure of 'branchiness' that I have devised to normalise a density estimate.  I would like to know if this corresponds to, or is related to, any pre-existing measures. I'm no expert in network science, and as such don't know what search terms to use.

The measure is best described with a diagram:

Start with a point, $a$, somewhere on the graph. Move an increasing distance away from $a$ and measure the number of shortest-distance branches that are possible at this distance. Once a branch terminates (as is the case for cul de sacs/dead ends in the road network), it is no longer counted. Repeat for many points on the network (e.g. point $b$ illustrated in the figure).

If I generate many traces for many points on the network, as shown in the top panel of the figure, the mean trace should appear smooth(?).  I'm interested in whether this mean "distance<->branches" relationship has a name. It seems to be related to betweenness, but I don't think it's the same thing.


texts: What is the nomenclature or theory for determining an overall status of multiple enumerations?

texts:
I am writing a method which evaluates multiple status enumerations and determines an overall status. I'm looking for what this process might be called and perhaps some theory on it.

It may be best to provide an example. Consider an alarm system, where individual sensors report one of three states:

Alarm
Safe
Unknown

If any individual sensor reports Alarm, the state of the entire system might be considered to be Alarm. Depending on design requirements, if any sensor reports Unknown the overall system state might also be Unknown or Alarm.

Is there an article or encyclopedia entry that discusses the above process of evaluation? What is this type of processing called?


texts:
A DPDA which accepts by empty stack cannot accept all Regular Languages?
Is it true that the DPDA cannot accept all regular languages?

I am not able to understand this.As per my knowledge DPDA are more powerful than regular languages as they have finite automate and also the stack.So finite automate can handle all the regular languages.So why above statement is true?


texts:
I am trying to prepare for a test comping up on run-time analysis.  I have been hit with a for loop that is throwing me a bit.  I am hoping someone can help me.

the loop is

for(j=1; j< n; j=j*2)

J is increasing at an increasing rate so it will be less than n/2  however I am having trouble concluding what exactly it will be.


texts: consistent heuristic - does it always exist?

texts:
I am studying for an artificial inteligence class, and i have to classify the following sentence

"For any search space, there is always an admissable and consistent A* heuristic".

Well, i know that there is always an admissable heuristic, for example zero, since its an underestimation of the real cost (althoug this would lead to uniform cost instead of a*).

What I would like to know is if there is always a consistent heuristic, and why.

Thanks for your help


texts: How to create an algorithm when given the invariant

texts:
I am given the following invariant:

Invariant The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array.

I am supposed to create a sorting Algortihm using this invariant. But I seem to have understood the concept of an Invariant differently, because with the information I find online, I can't find an idea for starting this problem.
Do I have to create an algorithm that sorts the first $n-1$ elements in the array? Thanks for your help


texts: Proving following problem NP Hard using known NP Hard partition problem

texts:
Least cost travel by intermixing different airline routes having linear discount functions:

Lowest air fare route chosen by mixing different routes provided by different airline having different discount functions (like some airline can give 25% discount if fare crosses $5k) so that total cost of travel is minimized after intermixing of different airline routes

This is a graph problem. Let $E(k)$ be the set of edges/routes
flown by $k$-th airline, also given cost of travel associated with
each edge.

For $n$ airlines we have $n$ sets of edges i.e $E(k)=\{\mbox{some edges}\}$ for
all $k=1.. n$. We need to find the route from given source $s$ to given destination $t$
such that we end up paying least fare among all possible
routes. There is no restriction on number of edges in a route.

This is an NP-hard problem. How can I prove it?


texts: Clarify the steps: what happened in this mathematical modelling of TSP?

texts:
Source: http://examples.gurobi.com/traveling-salesman-problem

I don't get this part: (look at the source)

  $$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1$$

I get that $x_{ij}$ is equal to 3, but why the "> 2" ?

And what is the deal with subtracting 1 from a set? How do you even do that?

How come $|\{1,2,3\}|-1 = 3 > 2$   ?!?

Okay so:
$$|\{1,2,3\}|-1 = 2$$

So how is he allowed to write:
$$|\{1,2,3\}|-1 = 3 > 2$$

?

That is basically the same as writing: (which is incorrect right?) $$2 = 3 > 2$$

I don't get this part at all, please elaborate on what happened in as simple language as possible. My level is high school final math level.


texts:
I want to create a turing machine that describes the language L={x#y | x,y\in {0,1}* and x is a substring of y}.
However I'm not sure how to start writing the transition function δ as I've just gotten acquainted with turing, can you point me the transitions so I can draw the state diagram and understand more?


texts: Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

texts:
The question was asked in an interview, and I'm not sure if this is the most optimized answer, but here goes-

You have an undirected acyclic graph, where each node has a non-negative value x and the edges have 0 value. You need to find a path with any number of nodes on it such that the total sum of all node values is exactly k. There are N nodes in the graph. You can start at any node.

I gave the brute-force solution for this problem, which is basically do a dfs on each node until you find a valid "root" node, such that it has a path to one of the other nodes, with a total sum being k. The time complexity of this solution would be n^2, since we are doing DFS on each node.

The question was posed as a delivery problem, where you have N connected houses, each having a package of weight within the range 1 to k, and the truck can start at any house and should follow a path, and has to pick the package from every house that is on that path. The weights should sum exactly to k.


texts: What's a good algorithm for deleting multiple elements in a heap?

texts:
I have a binary min-heap, size n, and I want to delete a number of
elements, identified by some predicate.

Any algorithm needs at least n tests of the predicate (preferably,
exactly n), so the interesting performance metrics are the number of
moves of elements, and the number of additional tests of the
predicate.

One possible way is to first delete elements from the corresponding
array, using a single pass to delete elements and compact the array.
And then rebuild the heap from the array. Both steps are O(n). But as
far as I understand, the rebuild step can need n moves of elements
even if only one or two elements are deleted, if they are at unlucky
positions in the array.

I wonder if there's some good algorithm which

needs O(n) element moves in the worst case
needs few extra tests of the predicate, say total n + O(log n) tests
in the worst case
needs a lot fewer then n element moves in the special cases that
only a few elements are deleted, or only a few elements are kept.


texts: Encoding a "not-k-out-of-n" constraint for SAT solvers

texts:
I'm finding myself needing to encode a "not-k-out-of-n" constraint in a SAT solver.

The "at-most-k-out-of-n" constraint for SAT solvers is something I can find research about -- this paper by Frisch and Giannaros, for example.

Given an "at-most-k-out-of-n" tool, I can get an "at-least-k-out-of-n" tool by inverting all the terms.  With both tools, I can get a "k-out-of-n" tool by having both the "at-most-k" and "at-least-k" constraints.

But I don't see how I can encode a "not-k-out-of-n" constraint.  If I use "at-most-(k-1)" and "at-least-(k+1)", then obviously I'm going to get no solutions.

Is there a simple transformation here that I'm missing?


texts: A language is decidable iff some enumerator enumerates it in decreasing order

texts:
Show that a language is decidable iff some enumerator enumerates the language in decreasing order.

What does it mean by enumerator enumerating in decreasing order? I am so confused about this concept. Can you prove the above theorem? Please help me.


texts: Why there are no approximation algorithms for SAT and other decision problems?

texts:
I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the algorithm is not optimal, it will make errors.)

I cannot find any approximation algorithms for such problems. I was looking specifically for SAT and I found in Wikipedia page about Approximation Algorithm the following: Another limitation of the approach is that it applies only to optimization problems and not to "pure" decision problems like satisfiability, although it is often possible to ...

Why we do not, for example, define the approximation ratio to be something proportional to the number of mistakes that the algorithm makes? How do we actually solve decision problems in greedy and sub-optimal manner?


texts: If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$?

texts:
I tried to solve it as the following:
$$\overline{L}=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)\neq\Sigma^* \big\}$$
I'll show that $\overline{L}\not\in RE$ by reduction from $$\overline{A_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ rejects } w \big\}$$
I begin by assuming that $\overline{L}$ is recognized by some TM $M'$.

Next, I construct a machine $M_{\overline{A_{TM}}}$ that will use $M'$ to recognize $\overline{A_{TM}}$.

TM $M'$ on input $\langle M, w\rangle$:

Build TM $M_1,M_2$
Simulate $M_1,M_2$ on all $x\in\Sigma^*$, Any simulation will be at most $|x|$ steps.
If $M_1$ and $M_2$ reject the same $x$, then $M'$ will accept $\langle M, w\rangle$.
If $M_1$ or $M_2$ accept some $x$, then $M'$ will reject $\langle M, w\rangle$.

Therefore, $\langle M, w \rangle\in\overline{A_{TM}}$ exactly when $\langle M_1,M_2\rangle\in\overline{L}$.

Because $\overline{A_{TM}}\not\in RE$ so is $\overline{L}$, then $L\not\in co-RE$

Is it true and can I use similar approach to show that $L\not\in RE$?

Thanks.


texts:
If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)

Right now I'm building a KD-Tree of size M, so with N queries on that I end up using N log M time. Can I do better?


texts: Hint on median of two sorted lists, logarithmic time

texts:
I'm looking for a hint to help me think through/solve the problem of finding the median of two sorted lists/arrays in O(log(m+n)) time, where m,n are the sizes/lengths of each list, respectively.

I can immediately think of an obvious O(m+n) time algorithm using big-theta of m+n space, as follows: Merge the two lists into a new list in O(m+n) time. Find the middle element of that list in O(1) time (more particularly, if the merged list is even in length, take the mean of the floor of the element at index (m+n)/2, and the ceiling of the element at index (m+n)/2, otherwise the merged list length is odd and just use the element at (m+n)/2... potentially update logic for off-by-one depending on zero- or one-indexing).

But I don't immediately see how the median could be found in logarithmic time. Any hints would be appreciated!


texts:
We have an n-ary tree used for searching that we'd like to keep balanced.  It is currently mostly a B-tree without the balancing operations. The issue we have for implementing those is that each sub-tree has its own sorting criteria (chosen in a set of five, if that's important) and that the balancing algorithms we know don't work in that case.

Is there a known algorithm which work in that case?  Or for a variation, we would probably reduce the number of criteria -- but not to one! -- and ensure that all nodes at a given level are using the same criteria if that help to keep the tree balanced at a reasonable cost and avoid rebuilding the whole tree like we do in some cases.


texts: I would like to know how to modify DFS/BFS in order to return the number of the trees present in a graph. I know that a tree is an acyclic connected graph, and I think that I have to initialize a counter somewhere, but I don't know where. I made the procedure "is-tree(G)" where G is the graph. It returns true if the subprocedure "is-connected(G)" also returns true and if the number of the arcs in G = number of nodes in G - 1, otherwise the procedure returns false. At this point I don't know how to count all the possibile subgraphs which are also trees.


texts: Getting parallel items in dependency resolution

texts: I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent paths?


texts:
There is a convex polygon $X$ contained in another polygon $Z$ (which can be non-convex and even have holes). I would like to expand $X$ to a larger convex polygon $Y$ such that:

$X\subseteq Y\subseteq Z$
$Y$ is maximal, i.e, there is no other convex polygon $Y'$ such that $Y\subsetneq Y' \subseteq Z$

NOTE: $Y$ does not have to have maximum area; it only has to be maximal.

What is an algorithm for finding such $Y$?


texts: Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?

texts:
I am reading the naive conversion to CNF, this procedure is explaining in this book book, but I have not found a conplexity analysis of this algorithm:

elimination of equivalence
Elimination of Implications
elimination of double negation
De Morgan Laws
distributive law

I found one implementation of this method in this Repo https://github.com/netom/satispy

Thanks


texts: Finding the weakest precondition and invariant of while loop

texts:
I am trying to find the weakest precondition and invariant of this while loop. I have read and am trying to understand the concept of calculating preconditions based on postconditions. I was wondering if someone could explain it to me.

while i < j do
    i = i + 1;
    j = j - 1;
end

{i = j or i = j + 1}


texts: I'm interested in learning about how facial recognition works.  I'm especially interested in the algorithms or approach that is used.  What are the leading methods for facial recognition?  Is there a good overview or source to learn about a few of the most widely used algorithms for facial recognition?  What would be the best handful of research papers to read first?


texts: Set of Turing machines that halt after exactly 14 steps

texts:
Let $M_i$ be the Turing machine with Gödel number $i$. Let
$$A = \{i \mid M_i \text{ with input \(x\) halts after exactly 14 steps}\}$$
Is the set $A$ recursive?


texts:
I don't know where else to ask this question, I hope this is a good place.

I'm just curious to know if its possible to make a lambda calculus generator; essentially, a loop that will, given infinite time, produce every possible lambda calculus function. (like in the form of a string).

Since lambda calculus is so simple, having only a few elements to its notation I thought it might be possible (though, not very useful) to produce all possible combinations of that notation elements, starting with the simplest combinations, and thereby produce every possible lambda calculus function.

Of course, I know almost nothing about lambda calculus so I have no idea if this is really possible.

Is it? If so, is it pretty straightforward like I've envisioned it, or is it technically possible, but so difficult that it is effectively impossible?

PS. I'm not talking about beta-reduced functions, I'm just talking about every valid notation of every lambda calculus function.


texts: Can a Turing machine determine if a set is accepted by a another Turing machine?

texts:
Can a Turing machine $M_A$ determine if the Turing machine $M_B$ accepts the set $W_k$?

I am curious about the answer to this as I am thinking about using the truth value of it on using it for a recursive enumerability proof.


texts: Star notation for context-free language alphabet?

texts:
I noticed that some "design-the-grammar" problems say verbally

Alphabet is $\mathbf{\{0,1\}}$.
$\{w \mid w \text{ contains at least three 1s}\}$

and some problems list it as

$\{ w ∈ \mathbf{\{0,1\}}^* \mid w \text{ contains at least three 1s} \}$

So, my question is: Is the in-line notation with the asterisk star '*' (as in "$\{0,1\}^*$") equivalent to saying "alphabet is $\{0,1\}$", or are those alphabets different?


texts: What does "finding an optimal action" for a bandit mean?

texts: In Sutton and Barto's reinforcement learning book, in multi-armed bandit problem a phrase has been used. "finding an optimal action" using greedy/$\epsilon$-greedy algorithm. When it is said that an algorithm "finds the optimal action " ?


texts: In 1968 there were more than 3000 programming languages known, how large would this number be today?

texts:
Alan Kay stated in one of his talks that there was a paper in 1968 that listen at least 3000 programming languages that were known in the year 1968.

What would be an unsientific but "educated guess" on the number of programming languages that existed up till now?

(I.e., this number would assume that if a programming language ever existed it is counted in the total number of today)


texts: why valid-invalid bit is needed in simple paging system?

texts:
I am learning OS from Silberschatz book. I read the Valid-invalid bit in a process page table also. But I could not understand why valid-invalid bit is required. The pagetable is dynamically built as pages are mapped to frames. So all the entries in page-table are valid.

thanks


texts: What is a distributed algorithm for generating random "private" pair-matchings?

texts:
Say you have 2N named peers (agents) able to address each other by their name and communicate freely among them.
What distributed algorithm could they use in order to randomly pair up? The final situation would be that the agents were able to organize themselves in N random couples. On different runs the random couples should be different.
Important: the algorithm should be "private" in the following sense: at the end of the round, each agent should only know the name of agent it was paired with.
It's also important that the agents have no possible way to influence who they end up paired with.


texts: What is a visual bag of words and how is it implemented?

texts: I'm currently working on implementing a bag of visual words in Python. I get the general gist of how it works but I can't seem to find any sources that explain it in more detail to a level where I can implement it. I'm guessing scikit learn and scikit image would come in but I can't seem to point myself in the right direction. Any help?


texts: Are there any applications to use a halting decidable system to study security problems in distributed systems?

texts: There's a bounded system S (halting is decidable) that can be used to model reliable asynchronous communication and unreliable asynchronous communication. Are there any applications to use this system to resolve security problems in distributed systems?


texts: Why can't a programming language be both fully recursive and polymorphic

texts: In my theory of computation class last Spring my professor said in passing that a programming language cannot be both fully recursive and polymorphic. I didn't think much of it till now? What does it mean to be "fully" polymorphic and why does that mean you a language can't be "fully" recursive?


texts: Geometric median of two disjoint sets of points lies on line between their respective medians

texts:
I was working on a problem about geometric medians and I had an idea for a divide and conquer solution, but it would only work if a set of points, when split into two disjoint sets, and those sets respective geometric medians calculated and a line passed between, it holds that the geometric median of the overall set of points lies on that line. When graphing it and visualizing it, seems possible, and when I used existing algorithms and experimented, it seems to be very close but not quite on the same line. I am not sure if this is due to error in calculation of the geometric median or not.

I have some example Python code demonstrating how close the numbers are here: Geometric Median comparison

Any expertise in this matter would be appreciated.


texts: Equality checking mod $10$ via arithmetic circuits

texts:
I'm interested in implementing equality checking mod 10 in an arithmetic circuit.
Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it off.

First, note that if $\mathbb{Z}_{10}$ were a field, this would be trivial due to Lagrange interpolation (allowing us to construct a polynomial with roots in $\mathbb{Z}_{10}^\times$, and taking value $1$ at $x = 0$). I'm interested in this unfortunately more difficult case.

Traditionally, appealing to some variant of Fermat's little theorem would make sense.
Again, over a field $\mathbb{Z}_p$ we would have that $a^{p-1}\equiv 1$ if $a\neq 0$, and we'd be done.
Euler's theorem is an obvious thing to try:
$$
a^{\varphi(n)}\equiv 1\mod n,\quad (a,n) = 1
$$
This will map $\mathbb{Z}_{10}$ to $\{0,1,5,6\}$.
We then might want to try to map $1,5,6\to 1$ while keeping $0\to 0$, but I don't believe this will be possible via some polynomial function.

If some polynomial $p(x)$ existed that did do this, we could consider $p(0)$ and $p(6)$.
We have that $p(0)\not\equiv p(6)\mod 10$ (by assumption), and furthermore $p(0) = 0\not\equiv 1 =p(6)\mod 2$.
This seems like a contradiction, as $p(x)\mod q\equiv p(x\mod q)$, due to "mod commuting with finite products/sums", which are precisely what polynomials are.

This makes me doubt that equality checking mod 10 is possible to implement with an arithmetic circuit over $\mathbb{Z}_{10}$, but the problem was phrased to me in a way that it seems like it should be possible to do some way with arithmetic circuits. How would you do it?


texts: Which article in front of O(.), Ω(.), ...?

texts:
Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a $O(\sqrt{n}/\varepsilon^2)$ algorithm". And I am struggling to decide whether I should use "a" or "an" in front of these: is there a consensus/precedent?

(in hindsight, this may not be the best place to raise such profound questions; I was just unable to find any better one)


texts: Break keyword outside a loop is syntax error or semantic error?

texts:
I am designing a simple compiler for my university project. In my programming language, the break keyword is allowed.
I want to know whether break keyword occurs outside a loop should be a syntax error or semantic error. I want to know what is the best approach.
If it is a syntax error I can do it in the grammar file. But if it is a semantic one then I can do it in a pass. But I don't know which one is the better approach.


texts: In a machine learning system, why use differentially private SGD if our input data is already perturbed by a DP mechanism?

texts:
I'm trying to implement my own version of a deep neural network with differential privacy to preserve the privacy of the parties involved in the training dataset.
I'm using the method by Abadi et al. proposed in their seminal paper Deep Learning with Differential Privacy as the basis of my implementation. Now I have trouble understanding one thing in this paper. In their method, they propose a differentially private SGD optimisation function and they use an accountant to keep their privacy budget expenditure during each iteration. All of this makes sense: every time you query the data, you need to add controlled noise to it to mitigate the risk of leakage. But before they begin the training process, they add a differentially private PCA layer and filter their data through it.
My confusion is about why we do need to have DP-SGD after this (or the other way around, why DP-PCA when we're already ensuring DP with our DP-SDG method). I mean, based on post-processing principle, if a mechanism is say (epsilon)-DP, any function performed on the output of that mechanism is also (epsilon)-DP. Now since we're already applying an (epsilon)-differentially private PCA mechanism on our data, why do we need to have the whole DP-SGD process after that? I understand the problem with local DP and why it's much more efficient to do global DP on the model instead of the training data, but I'm wondering if we're already applying DP during the training phase, is it really necessary for the PCA to be DP as well or could we have just used normal DP or another dimensionality reduction method?


texts:
I was wondering if there are any calculus relationships implicit in Big-O notation.

For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step, and also involves looking at each part of the input a constant number of times. The derivative of a linear expression is a constant expression, so there is some hint of a pattern. However, I haven't been able to figure out how to generalize these facts to other Big-O classes of algorithms.

Do derivatives/antiderivatives help in matching an algorithm's Big-O description with its behavior?


texts: Help with Linear recurrence relation with balanced partition

texts:
In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with "partizione bilanciata" which means "balanced partition".

My course is in Italian and looking online in English I could not find any trace of this method, I know of the recursive tree, induction and master theorem.

Has anyone an idea of how this is called in English? I don't like studying in Italian and I do not understand those pdfs.

I'm attaching some images of the formulas.

What exactly "balanced partition" mean, does it have something to do with for example Quick Sort, when you choose a middle pivot and the partitions are equal in size, which means it's balanced ?

Is it the same as master theorem written maybe in a different way?
I can see the form of the recurrence relation is different than the master theorem:

The master theorem has $f(n)$ instead of $cn^\beta$.


texts: Finding the interior of a connected graph

texts:
I'm designing software that produces images such as the following:

Regions of interest are circumscribed by red pixels. I am interested in extracting the fully-enclosed pixel regions. Ultimately, I would like to calculate the approximate center, width, and height of the regions. Ideally, I would even like to eliminate interior loops--that is, only preserve the largest enclosing body of a region (a "region" being an isolated pixel group).

I have experience implementing search algorithms, so my first instinct is to traverse the edges until a loop is detected (arrival at the start); however, I recognize the potential for multiple solutions--alternate, valid loop possibilities--and then I would require a way to decide between them. Perhaps the one that is longer or encloses the greatest number of pixels.


texts:
I'm trying to understand this paper on computer vision (http://persci.mit.edu/pub_pdfs/elements91.pdf) and it talks about building a periodic table of things we can get from the plenoptic function. It says that by taking the partial derivative of it with respect to x you can get "vertical
"edge"" but I have no idea what that is supposed to mean (page 13, top diagram). Does anyone understand that part?


texts: Finding subsets in a large collection of sets

texts:
Given a large collection $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$, where each $X_i$ is a set of integers, what's a fast algorithm to identify all pairs $(i,j)$ with $i \ne j$ such that $X_i \subseteq X_j$?

The best I can think of is the following (rather naive) algorithm:

Sort each set $X_i$.
Sort $\mathcal{X}$ by cardinality (smallest to largest). Tag each set with its original position in $\mathcal{X}$.
For each pair $1 \le i < j \le n$, check if $X_i \subseteq X_j$. Since $X_i$ and $X_j$ are sorted, this can be done with a single linear pass, similar to the merging step of merge sort. If so, output the original positions of $X_i$ and $X_j$.

This takes $O(n^2m + nm\log m)$ time, where $m = \max_i|X_i|$.

I suspect it's possible to obtain some improvement, since by transitivity, not all $n(n-1)/2$ pairwise comparisons are always necessary. If it has been determined that $X_i \subseteq X_j$ and $X_j \subseteq X_k$, then $X_i \subseteq X_k$ is known with no additional work. Similarly, if $X_i \not\subseteq X_k$ and $X_i \subseteq X_j$, then $X_j \not\subseteq X_k$. However, to take advantage of this, I need a fast way to notice that transitivity (or a transitivity violation) has occurred.


texts: What is the role of Numerical Gradient Computation in Backpropagation algorithm?

texts:
I was listening CS231n (2017) lectures and noted that there is a lot of attention to Numerical Gradient Computation (NGC). It starts @5:53 in this video and appears a few times later.

Also, looking at the batch normalization materials (example), I found a lot of attention drawn to exactly the same topic (well, probably because it is the same backpropagation...).

As I understood, gradients we use in various optimization methods (vanilla SGD, Adam) require us to know activation function derivative. I suppose, if the activation function is complex or we are lazy enough to take derivative analytically, we need to compute gradient numerically and that is where we use NGC.

Questions:

Is that the only purpose of NGC in backpropagation?
Isn't it faster to use analytically form of the activation function derivative to calculate gradients?


texts: How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances?

texts: In recent SAT competitions, there is a Certified UNSAT track. The problem instances are all unsatisfiable and the solvers are asked to produce certificates for unsatisfiability. One way is to produce a resolution refutation for the set of clauses in a problem instance. How can a SAT solver, say MiniSAT, be modified to do this? Can this be done for every solver? I searched the Internet and found little information. A reference is good for me.


texts:
The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication algorithm".

But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that the division has the same complexity as multiplication?

If I use, say, Karatsuba multiplication algorithm, will the division also take $O(n^{1.585})$


texts: The problem of equivalence of a CFG and a RG?

texts:
Given a context-free grammar and a regular grammar, check whether they are equivalent.
It's a fact that it's undecidable, but how could I prove it?

I want to clarify that my question is not about determining whether a CFG describes a regular language. In my problem I am given a CFG and a regular language  and I need to tell whether they are equal or not. These are different problems as far as I understand, mine is easier than that one.


texts: Multicommodity shortest path problem on a directed acyclic graph

texts:
I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the shortest paths to transport the commodities between their respective source-sink pairs.

Is there any algorithm that can solve this kind of problem rapidly, possibly using topological sorting first? How is this affected if there is unlimited/limited capacity on the arcs?

Many thanks!


texts:
Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc.

Note: It is okay if it generates only graphs with a minimal node degree of 1 or 2.


texts:
I have two series of tuples

$$
A = \{(x_0,t_{01},t_{02}),(x_1,t_{11},t_{12}),\ldots,(x_n,t_{n1},t_{n2})\} \\
B = \{(y_0,tt_{01},tt_{02}),(y_1,tt_{11},tt_{12}),\ldots,(y_m,tt_{m1},tt_{m2})\}
$$

where $m \neq n$ and $t$ and $tt$ are both time observations. $t_{i1}$ and $tt_{j1}$ are both the start of some epoch for arbitrary $i$ and $j$. $t_{i2}$ and $tt_{j2}$ are both the end of some epoch for arbitrary $i$ and $j$. $x_i$ and $y_j$ are the observations of a sensor during those epochs.

In my case $t_{i1}$ and $tt_{j1}$ are not guaranteed to match, nor are $t_{i2}$ and $tt_{j2}$. However, they do represent time epochs that overlap with each other. For instance if $t_{11}$ and $t_{12}$ stretches from 2015-01-02 to 2015-01-03 then $tt_{11}$ and $tt_{12}$ might go from 2015-01-01 to 2015-01-04.

What I'm hoping to do is align the observations $x_i$ and $y_j$ temporally into a single sequence that might look like

$$ C = \{(x_0,y_0,ttt_{01},ttt_{02}),(x_1,y_1,ttt_{11},ttt_{12}),\ldots,(x_p,y_p,ttt_{p1},ttt_{p2})\}, $$

where $p$ is the last observation in the sequence and the time observations $ttt_{k1}$ and $ttt_{k2}$ are the start and end of some epoch non-overlapping with later observations of $ttt_{\mathit{whatever}}$.

I've already looked into some of the papers available on the subject and all of the work I've seen deals with image analysis, audio overlap, kernels, and others that seem a bit off focus than what I'm looking for. Is there more basic theory available that deal specifically with the situation I'm describing here? Or is my case just a specific one covered by some of the papers that I've been reading on?