texts: An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each vertex is incident to an odd number of edges. Is anything similar studied in Computer Science?


texts: 3-Dimensional Matching with at Most $2n$ Hyperedges

texts:
In 3 dimensional matching, we are given a set $M\subseteq X\times Y\times Z$ where $|X|=|Y|=|Z|=n$. A matching in $M$ is a subset $T⊆M$ such that no elements in $T$ agree in any coordinate. The goal is to find a matching in $M$ of size $n$.

If we assume that $n\leq|M|=m<2n$, can we solve 3DM in polynomial-time?

I know that in a 2-bounded instance of 3DM, 3DM can be solved in polynomial-time. The 2-bounded instance is when no element appears in more than two triples in $M$. For $m<2n$, we do not necessarily have a 2-bounded instance.

Further, in a 3-bounded instance of 3DM, 3DM is NP-hard. The 3-bounded instance is when no element appears in more than three triples in $M$, that is $m\leq3n$.


texts: How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm?

texts:
I can't see how I can apply quantum function $a^x\mod N$ to initial states. Explanations of Shor's algorithm often skips this part, and I do not see what unitary matrix this algorithm would correspond to.

reference: https://en.wikipedia.org/?title=Shor%27s_algorithm


texts: Searching for multiple elements of an array

texts:
Suppose we have two sorted arrays $A$ and $B$, and we want to find the indices in $B$ of all elements of $A$. We can do this in $\mathcal O(|A|\log|B|)$ time by simply binary searching $|A|$ times. We can do it in $\mathcal O(|A| + |B|)$ time by iterating through the arrays together like the merge phase of a mergesort; this may or may not be an improvement, depending on the sizes of $A$ and $B$.

Can we do better? I don't expect any substantial improvement for $|A| \in \mathcal O(1)$ or $|A| \in \mathcal O(|B|)$, but for, say, $|A| \in \mathcal O(\log |B|)$, can we do better than $\mathcal O((\log |B|)^2)$? My ideas so far have been about some sort of adaptation of binary search that divides $B$ into a number of intervals depending on $|A|$, but I'm not yet sure whether it's an improvement.


texts: What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another?

texts:
So i came upon this thread :

https://gateoverflow.in/57631/relation-between-np-recursive-and-recusive-enumerable

and the guy says  Every language in NP is recursive and Every language in NP is recursively enumerable.

but i dont get it, isn't NP the set of problems which we can only determine if a given answer is true  in polynomial? doesn't that mean if the answer is no we may not know?

So i'm kinda confused here and really can't put all these together

so overall my question is : can someone please tell me what is the relation between NP/NP-hard/NP-complete problems and Recursive/RE languages ?

i read about these stuff in different courses but non of them combined all of them together for a bigger picture

(also i know that Recursive languages are a subset of RE)

also based on this :
https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

NP should not be recursive because NP is set of problems which IF the answer is yes we can detect it in polynomial, but that thread doesn't say anything about what happens if its not  NP


texts: Metagame Paradox: what is wrong with this explanation?

texts:
Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post content: definition - proposed solution - conclusion)

Something is a game iff:

G1. Two players
G2. Players alternate
G3. The game finally ends.

The metagame is:

M1. First player picks a game
M2. Second player starts the game
M3. The winner is the winner of the game at step 2.

Example of a metagame:

1) I pick tic-tac-toe
2) OK, I put X here ..
.. so they play ..
3) .. and let player 2 wins in the tic-tac-toe => player 2 wins the metagame.

Paradox: Is metagame a game?

If metagame is a game, then at point (M1) both players can always pick a metagame, so the metagame will never end => (G3) is violated => metagame is not a game => contradiction.

(also contradiction for case "metagame is not a game" -- metagame will satisfy the definition of a game)

(see also http://www.math.cornell.edu/~mec/2006-2007/Games/hypergame.html)

What is the solution to the paradox?

UPDATE: You may want to skip this explanation and go directly to D.W. answer.

I came up with the following explanation:

Lets formalize the problem using Turing Machines notations.
Let a game be a finite binary string that describes "somehow" game rules. Let a game simulator be a non-deterministic TM that reads a description from the input (without any sanity checks, so the TM doesn't know if the game finally ends), and then makes non-deterministic moves for the first and second player. Here we assume (A1) that the game-simulator can decide valid next moves.

Now have a look at the description of a meta-game:

M1. First player picks a game

This sentence means that we can "pick a game", i.e. in the definition we assume (A2) that whether an arbitrarily binary string is a game (satisfies G1,G2,G3) is decidable. (see also note (n1) )

M2 and M3 look decidable.

So, my suggestion is that metagame is not "defined properly", since its definition assumes the existence of a decider "if a given binary string is a game". And then we derive a contradiction, so this assumption is wrong.

Does it make sense? Is this related with other explanations of the paradox?
(intuitive answers would be great!)

Notes:

Assuming "whether an arbitrarily binary string is a game" may be too much. But we need some computable procedure "pick a game" and one that came into mind is "generate random string, check if it is a game".
I don't know what is a formal word for "not defined properly"
Assumption A1 may also be undecidable, but I believe it should not change the argument..


texts: Determine if there's a $P_3$ as an induced subgraph in a graph $G$

texts:
Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices).

What I was thinking at first is that any vertex $v$ that has at least two neighbors could indicate a $P_3$ but it wouldn't be induced since these two neighbors might be connected. So that would mean I would have to iterate over all pairs of neighbors of every vertex to determine if they're connected and I would exceed the requested runtime. Plus, that way I would actually be able to not only tell if there's a $P_3$ but also find it, which kinda tells me this isn't what I should be doing.
Any suggestions? Or hints?


texts: Can someone explain how do we find these parity bit errors?


texts: Are Synchronous Message Order and Total Message Order separate concepts?

texts:
I am currently studying this book on distributed systems. In the chapter on message ordering the authors appear to use the term total message ordering and synchronous message ordering interchangeably. It make sense why the authors may have done this. As far as I undertand a synchronous message-passing system enforces a total-order on all messages in the system.

Are they, in fact, one and the same concept? Or are these disparate concepts, and one of the properties just implies the other?


texts:
The number of computations of an algorithm is $n'm\sum_{x=0}^{n'-m} 1/(m+x)$. What is the complexity of the algorithm ?

Thanx for help.


texts: What's the least signifcant bit of a mantissa system?

texts:
If Mantissa is a 1-dot-M fixed-point number whose most significant bit is always  1 then, how is the least significant bit calculated?

I know the least and most significant bit of the mantissa results in the following range:

1.0 <_ Mantissa <_ (2.0 - 1/2^M)

But specifically, I don't understand where the 2 comes from.


texts: State machine to convert from base 2 to base 10?

texts: Is there a state machine which can convert base 2 decimals to base 10 decimals in a streaming fashion? Integers?


texts: High Level Programming Languages vs Block Programming Environments

texts:
I am looking for the opinions of more experienced programmers as to the effectiveness of writing programs in Block Programming Environments such as Scratch or App Inventor as opposed to High Level Languages such as C++, Python or Java.
I have already done some research and here are some examples of links that have been helpful.

Programming : High Level Languages
An Overview of Programs and Programming Languages

I am just looking for a few other peoples opinions.

Questions that I would really appreciate if you could answer include:

Do you find using high level code easier or more difficult than using blocks?

Have you experienced any limitations of either High Level Languages or Block programming?

What advantages and disadvantages have you experienced when using the two?

Any helpful answers would really be appreciated


texts: Finding the values for a particular bucket in a list

texts:
I have a list of n items. I need to find the items that will be present in a given range, if the list were to be sorted. Sorting the entire list is not required and not desired, the buckets can be evenly spaced, but if an approach can handle a particular bucket starting at index i and ending at index j it would be preferred.

The ultimate goal is to have a sorted subset starting from index i and ending at index j. Though for the above problem sorting isn't required.

Example:

i := 2
j := 4
a := [9,0,1,8,2,7,3,6,4,5]
b := selectBucket(a, i, j)

[2,3] // b
[3,2] // also could work

I found an answer about dividing a list into k buckets, this approach is alright, but if there is a better way to get only a single bucket it would be preferred (that is of course faster).


texts: Given an amount of sets with numbers, find a set of numbers not including any of the given

texts:
Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the whole set) For example :Setting the max number 8 and given the sets

{1,2}
 {2,3}
 {7}
 {3,4}
 {5,6,4},
one maximum solution is the set {1, 3, 5, 6, 8}. I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem, but that seems to work only if the sets were consisted only from pairs,which doesn't stand.Any idea?Thanks in advance.


texts: Searching for the underyling affine transformation in a ridge function

texts:
Quoting from Wikipedia:

A ridge function is any function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ that can be written as the composition of a univariate function with an affine transformation, that is: $f(\mathbf{x})=g(\mathbf{x}\cdot\mathbf{a})$ for some $g:\mathbb{R}\rightarrow\mathbb{R}$ and $\mathbf{a}\in \mathbb{R}^d$.

This has the property that there are $d-1$ dimensions in which the ridge function is constant.
This led me to wonder the following questions:
What would be the most efficient algorithm to find $\hat{\mathbf{a}}=\mathbf{a}/|\mathbf{a}|$, the sole direction in which $f$ is not constant, when you can only query the function $f$; and what are the least restrictive conditions on $g$ to enable finding $\hat{\mathbf{a}}$? (The algorithm is also given a error bound $\epsilon\in\mathbb{R_{>0}}$, such that the algorithm is only required to find an $\hat{\mathbf{a}}_{approx}$ such that $|\hat{\mathbf{a}}_{approx} - \hat{\mathbf{a}}|<\epsilon$.)

I can imagine a gradient ascent on the magnitude of $h(x)=\partial f(\mathbf{y} + x\hat{\mathbf{x}})/\partial x$,  as you vary $\hat{\mathbf{x}}\in \mathbb{R}^d$ (where $|\hat{\mathbf{x}}|=1$, $\mathbf{y}\in \mathbb{R}^d$ is fixed, and $x\ll |\mathbf{y}|$, $x\in\mathbb{R}$). In this case, the only requirement on $g$, then, is that its derivative is defined at $\mathbf{y}\cdot\mathbf{a}$.
But is there a more efficient algorithm, and how do the resources required for that algorithm scale with $d$ and error $\epsilon$?

(Side note: The problem is equivalent to determining the weights of a single-layer neural network whose single output neuron has a ridge activation function, solely by monitoring the single neuron's output.)


texts: What is the difference between Moore's algorithm and partition refinement algorithm for DFA minimization?

texts: Both the algorithms use the partition method to minimize the DFA. I cannot understand the difference between them. Can someone give an example where we can see the difference between them.


texts:
I'm just a little confused about the wordings for reductions and would appreciate some help as I am very new to reductions.

I have a question where I have two sets, A and B, and I have to provide a reduction A $\leq_p$ B and then I have to prove that the reduction is correct.

What does this mean exactly?

For the reduction portion do I have to:

Provide some sort of explanation of B in terms of A?
Provide some sort of explanation of A in terms of B?
Both 1 & 2?

And then I'm assuming to prove the reduction is correct, I need to show A $\implies$ B as well as B $\implies$ A?

(The exact question has A as the set of un-directed graphs with a Hamiltonian path and B is the set of un-directed graphs with a Hamiltonian cycle)

Any clarification would be greatly appreciated!!

Thanks.


texts: Greyscale image to binary image conversion using operations on pixel

texts:
Previously, I tried convert a color image into a greyscale image by using pixel values of an image from a simple formula :-

Grey = 0.3*Red + 0.58*Green + 0.11*Blue

After that, I wanted to convert the greyscale image into a binary image & I used two different techniques :

NOTE : Red, Green & Blue are variables storing Greyscale intensity of the Pixel.

1. Algorithm 1:

if Red <= 127:
   Red = 0
   Green = 0
   Blue = 0
else:
   Red = 1
   Green = 1
   Blue = 1

2. Algorithm 2:

if Red <= AvgIntensity:
   Red = 0
   Green = 0
   Blue = 0
else:
   Red = 1
   Green = 1
   Blue = 1

where, AvgIntensity represents the average intensity of all the pixels of the image.

(Obviously,) the algorithms turned out to be wrong, producing incorrect output. So, I wanted to know about the correct way for greyscale to binary image conversion.


texts: Two-Sum - Range Allowance Algorithm Design

texts:
What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity?

Optimize for runtime over memory complexity.

The same item cannot be selected twice.

Inputs

An Int representing the total capacity
An Int representing the range above and below the total capacity sums are allowed to be within.
An Array of Int's representing items' individual capacities.

Output: A Boolean representing whether it is possible for two of the items to equal the total capacity plus and minus the given range.
Samples
1.

Input: [4, 5, 2, 6]
Total capacity: 10
Range Allowance: 0
Expect: true because 4 + 6 equal 10.

2.

Input: [4, 5, 2, 5]
Total capacity: 12
Range Allowance: 2
Expect: true even though there are no two numbers that equal 12 directly, there are two numbers that sum to 10 which is within the range allowance provided.

3.

Input: [4, 5, 2, 7]
Total capacity: 14
Range Allowance: 1
Expect: false


texts: Karger's min cut and tips on bounding nonlinear recurrences

texts:
I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a recursive version of the randomized edge contraction algorithm to help with the shrinking the error probability and ultimately help with an efficient algorithm for getting the global min $k$-cut with probability $1/2$.
Most of the analysis was going well until I started to analyze the probability of success of the recursive algorithm. I found that this probability was ultimately described as
$$P_i \geq P_{i-1} - \frac{1}{4} P_{i-1}^2$$
where $P_{i}$ is the probability of success on some call of the algorithm at level $i$ of the recursion tree, with a leaf having $i = 0$. One could show that the depth of the tree was $d = \frac{c \log_2(n)}{(k-1)}$ for some constant $c$ and ultimately I was looking to lower bound $P_{d}$. However, I struggled to lower bound this recurrence. I knew from studying the algorithm for a min cut that this recurrence should have the lower bound $P_{d} = \Omega(1/\log(n))$. I wanted to try and show this but the best I got on my own was doing
\begin{align}
P_{i} &\geq P_{i-1} - \frac{1}{4} P_{i-1}^2 \\
&\geq P_{i-1}\left( 1 - \frac{1}{4}\right) \tag{ $P_{i-1} \leq 1$ } \\
&= \frac{3}{4} P_{i-1} \\
&\geq \left(\frac{3}{4}\right)^{i} P_{0}
\end{align}
which, when we evaluate $P_{d}$, gives us that
\begin{align}
P_{d} &\geq (3/4)^{d} P_0 \\
&= (4/3)^{-c \log_2(n)/(k-1)} \\
&= n^{-\frac{c}{(k-1) \log_{4/3}(2)}} \\
&\geq n^{-\frac{2.41 c}{(k-1)}}
\end{align}
This is a much worse lower bound than what can be found. After this point, I investigated the original paper for the recursive randomized min cut algorithm. The trick they used was to perform a nonlinear change of variables to the recursion, something of the form $P_{k} = 4/Z_{k}$, where $Z_{k}$ is the new recurrence variable. This change leads to a new recurrence of the form
$$Z_{k} \leq Z_{k-1} + 1 + 1 / (Z_{k-1} - 1)$$
Since $Z_{k} = 4 / P_{k} \geq 4$, this implies we can upper bound the above recurrence as
$$Z_{k} \leq Z_{k-1} + 2 \leq 2 k + Z_{0} = 2 k + 4/P_{0}$$
which finally implies that indeed $P_{d} = \Omega(1/\log(n))$. I see that this transformation worked, but I do not have intuition for why one might think to try such a transformation. Can anyone help me with that intuition? Are there any other useful tips for tackling bounds of nonlinear recurrences?


texts: Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

texts:
Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below?

Fact 1: For monotone submodular functions, Nemhauser, Wolsey and Fisher proved [1]  that simple greedy algorithm gives $1-1/e$ approximation guarantee.

Fact 2: For non-monotone non-negative submodular functions, Buchbinder et. all proved [2] that randomized greedy algorithm gives $1/e$ approximation for cardinality constraint.


texts: Without primes in $P$ does integer factorization lie in $coNP$?

texts:
In integer factorization we ask 'Given $N$ is there a $a\in[2,\sqrt{N}+1]$ such that $a|N$?'.

Is the above problem in coNP because we know primes is in $P$?

That is there is no such factor $a$ of $N$ iff $N$ is prime and we have AKS certificate.

So was it not known prior to 2004 that integer factoring was in coNP?


texts:
What does $\log^{O(1)}n$ mean?

I am aware of big-O notation, but this notation makes no sense to me.
I can't find anything about it either, because there is no way a search engine interprets this correctly.

For a bit of context, the sentence where I found it reads "[...] we call a function [efficient] if it uses $O(\log n)$ space and at most time $\log^{O(1)}n$ per item."


texts: Finding the smallest number that scales a set of irrational numbers to integers

texts:
Say we have a set $S$ of $n$ irrational numbers $\left\{a_1, ..., a_n\right\}$.

Are there any known algorithms that can determine a scaling factor $s \in \mathcal{R}$ such that $s * a_i \in \mathcal{N} \;\forall a_i \in S$, assuming that such factor exists? If multiple exist, how about the smallest one?

Moreover, I wonder, under what input conditions could one assume that an algorithm for this problem can't (or can) return a valid scaling factor?


texts:
On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy

it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B"

What is a "Turing machine in class A" for classes P, NP, and coNP?

I'm guessing a Turing machine in P is a deterministic Turing machine that can only run for polynomial time in the size of its input

and that a Turing machine in NP is a nondeterministic Turing machine that can only run for polynomial time in the size of its input

But I have no clue what is a Turing machine in class coNP ?


texts: Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?

texts:
I've stumbled on this definition on Wikipedia, and I can't figure out why.

I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $2^n=x$. If I rewrite the expression with logarithms, I find $\log_2x = n$, so the base-2-log of the total number of possible combinations of 0 and 1 is $x$.

And I'm stuck here. I'm probably seeing this from the wrong angle. Also, I wonder what is that $+1$ for?

Sorry if it's a dumb question, but the only way I can memorize a formula is to give a meaning to its numbers.


texts: Difference between conflict serializability and view serializability

texts:
In my understanding both of them can be converted to serial schedules. (This helps with consistency by isolation property while also giving the performance boost by concurrency).

I'm  unable to understand one of the lines in this text:
http://infolab.stanford.edu/~ullman/dscb/vs-old.pdf

  Intuitively, view-serializability considers all the
  connections between transactions T and U such that T writes a database element
  whose value U reads. The key difference between view and conflict serializability
  appears when a transaction T writes a value $A$ that no other
  transaction reads (because some other transaction later writes its own value for
  A). In that case, the $w_T(A)$ action can be placed in certain other positions
  of the schedule (where $A$ is likewise never read) that would not be permitted
  under the definition of conflict-serializability.

I understand that the circumstances that can cause inconsistencies (if transactions are swapped) and affect the conflict serializability are
write(Q) by T1 and then write(Q) by T2, or
read(Q) by T1 and then write(Q) by T2, or
write(Q) by T1 and read(Q) by T2.
It seems to me that some special cases are allowed as per view serializability but I've not been able to pin point those cases. Any help is appreciated.


texts: Non-deterministic time hierarchy theorem: universal TM overhead

texts:
I am currently reading the book of Arora and Barak on computational complexity.
In the third chapter (p69-70), two classic theorems regarding time complexity hierarchies are introduced:

$\left[f(n)\log(f(n)) = \mathcal{o}(g(n))\right] \Rightarrow \left[DTIME(f(n) \subset DTIME(g(n))\right]$
$\left[f(n+1) = \mathcal{o}(g(n))\right] \Rightarrow \left[NTIME(f(n) \subset NTIME(g(n))\right]$

The proofs that are given for these theorems make use of (lazy) diagonalization of a universal TM that flips the answer.  This presumes we can simulate a TM $M$ that runs in $f(n)$ time using a universal TM $U$ that runs in $g(n)$.  For the deterministic case, this is possible, as the overhead of the universal TM is logarithmic (so for large enough $n$, we have $T(n) = f(n)$ and $U(n) = g(n) > f(n)\log(n)$).  For the non-deterministic part however, the $\log$ factor is dropped.  Could someone explain to me why the $\log$ factor isn't needed in this case?

The proofs of the book don't really help, as they only prove the theorem for the specific case in which $f(n) = n$ and $g(n) = n^{1.5}$.


texts:
I know that there is no algorithm for converting any logical formula to DNF so even though we have an efficient algorithm to solve DNFSAT we can't solve formulaSAT in deterministic polynomial time.
But what makes the finding of an efficient CNF algorithm solve formulaSAT in polynomial time?
Because I'm guessing that the complexity of converting a logical formula to a DNF would be the same as the complexity of converting a formula to CNF so even if we find an efficient algorithm for CNFSAT we won't be able to convert any formula into CNF and therefore we can't solve formulaSAT also! Or am I wrong and the problem of formulaSAT is not in NP?!
An example of what I mean by a formula: (¬A∨B)∧¬((A∧¬C∧(B∨D))∨(C∧D))


texts: smallest circle that covers two points with its center in x axis

texts:
I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know how to solve it mathematically.

  Give two planar points p1=(a1,b1) and p2=(a2,b2) and a line y=0,
  design an algorithm to find the smallest circle that covers
  both points such that its center (x*, 0) lies on y=0.


texts: Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $

texts:
I'm trying to prove the irregularity of the following language:
$$L = \{ a^mb^nb^n \mid nm \ge 3 \} $$
I tried to demonstrate that it doesn't verifies the Pumping Lemma but for all words I tried it seems to accept all of them.
Any hints or suggestions?


texts: Over every non-empty alphabet there exist languages which are non-regular

texts: I am not sure about the answer. Intuitivly I would say that there are alphabets for which there are no non-regular languages. In particular I am thinking of languages with only one element. But I am not sure.


texts: EM algorithm - What happens with the standard deviation?

texts:
What have you tried?
So I watched this video.
According to the video, we've to calculate the variance $\sigma^2$ as follows:
$$
    \sigma_{k}^{2} =
    \frac
        {
            p_{1} \left(x_{1} - \mu_{k_1}\right)^{2} + \ldots + p_{n} \left(x_{n}
                - \mu_{k_n}\right)^{2}
        }
        {
            p_{1} + p_{2} + \ldots + p_{n}
        }
$$
Where

$k$ is the index of the current Gaussian class.
$p$ represents the possibility of one point of the set
$n$ is the amount of points in the set

So what's your question?
I don't understand, why we have to use $\mu_{1}$, $\mu_{2}$, $\ldots$,
$\mu_{n}$. I expected to calculate it follows:
$$
    \sigma_{k}^{2} =
    \frac
        {
            p_{1} \left(x_{1} - \mu_k\right)^{2} + \ldots + p_{n} \left(x_{n}
                - \mu_k\right)^{2}
        }
        {
            p_{1} + p_{2} + \ldots + p_{n}
        }
$$
Because why do I have to use the "current-calculated" mean of the Gaussian and
not the "final" one?


texts: Solving a problem related to convolution

texts:
I have this confusion related to solving this problem

  You’ve been working with some physicists who need to study, as part of their experimental design, the interactions among large numbers of very small charged particles. Basically, their setup works as follows. They have an inert lattice structure, and they use this for placing charged particles at regular spacing along a straight line. Thus we can model their structure as consisting of the points $ \{1, 2, 3, \cdots , n\}$ on the real line; and at each of these points $j$, they have a particle with charge $q_j$. (Each charge can be either positive or negative.)

  They want to study the total force on each particle, by measuring it and then comparing it to a computational prediction. This computational part is where they need your help. The total net force on particle $j$, by Coulomb’s Law, is equal to

  $F_j = \sum_{i<j}\frac{Cq_iq_j}{(j-i)^2} - \sum_{i>j}\frac{Cq_iq_j}{(j-i)^2}$

  They’ve written the following simple program to compute $F_j$ for all $j$:

For j = 1, 2,...,n
   Initialize Fj to 0
   For i = 1, 2, ..., n
￼     If i < j then
       Add Cqiqj/(j-i)^2 to Fj
     Elseif i > j then
       ￼Add −Cqiqj/(j−i)^2 to Fj
     Endif
   Endfor
   Output Fj
Endfor

  It’s not hard to analyze the running time of this program: each invocation of the inner loop, over i, takes $O(n)$ time, and this inner loop is invoked $O(n)$ times total, so the overall running time is $O(n^2)$.

  The trouble is, for the large values of $n$ they’re working with, the program takes several minutes to run. On the other hand, their experimental setup is optimized so that they can throw down $n$ particles, perform the measurements, and be ready to handle n more particles within a few seconds. So they’d really like it if there were a way to compute all the forces $F_j$ much more quickly, so as to keep up with the rate of the experiment.

  Help them out by designing an algorithm that computes all the forces $F_j$ in $O(n \log n)$ time.

I am sure that this problem is solved by convolution which takes time $O(n \log n)$. However, I am not being able to proceed and see how it's converted to a problem related to convolution. Any suggestions?


texts: What are common techniques for reducing problems to each other?

texts:
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as some other problem $L_2$ by mapping instances from $L_2$ to solution-equivalent ones in $L_1$. Essentially, we show that any solver for $L_1$ can also solve $L_2$ if we allow it to use the reduction function as preprocessor.

I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?

What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!


texts: Finding Worst and Best Case Hit Rate of a Cache Given Code

texts:
I'm doing some practice problems to study and came across this one:
Consider a 8-way set associative cache with 64 B blocks, and 64 total blocks as part ofa 16 bit physical address.
Imagine we use the cache for the below assembly (RISC-V) code:
.data:arr:
  .byte 0, 1, 2 , ...  255 # All values from 0 to 255
.text:
   #ASSUME A WORKING PROLOGUE
   la a0 arr
   li a1 256
   #Scramble randomizes the elems of arr
   jal scramble
   #Assume t0 = 0, t1 = 256, s0 = A, s1 = B, s2 = C
   #START OF HIT RATE
Start:
   beq t0 t1 End  #Iterate 256 times
   add t2 a0 t0
   lbu t2 0(t2) #t2 = arr[t0]
   add t3 s0 t2
   lw t3 0(t3)  #t3 = A[t2]
   add t4 s1 t2
   lw t4 0(t4)  #t4 = B[t2]
   add t3 t3 t4
   add t4 s2 t0
   sw t3 0(t4)      # C[t0] = t3 + t4
   addi t0 t0 1
   j Start
   #END OF HIT RATE
End:
   #ASSUME A WORKING EPILOGUE

Let scramble a function that randomly sorts the elements of an array.  Additionally assume that:

A is located at 0x1000
B is located at 0x2000
C is located at 0x3000
arr is located at 0x4000
Our cache is empty when reaching #START OF HIT RATE

The question asks:

What is the best and worse case hit rate for this code?  Write your answer as a
fraction.

It says the answer are both 63/64. But how? the best case one especially doesn't make sense, because in the best case you only swap a few elements in scramble. In any case, how do you compute that number?


texts: Example of decidable set whose preimage is not decidable

texts: I know that if a set is a decidable, there exists an algorithm that enumerates it and prints value 1 if a given element belongs to the set and 0 otherwise. Therefore, its image is decidable, too. I think, though, that this is not true for the preimage of of the set under a partially computable function. Can someone provide an example that might help me to understand it, please?


texts: Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling )

texts:
Consider the following processes :

1) My First Question is if we need to schedule them using preemptive priority scheduling with Round-Robin for equal processes priorities with a quantum of 3. Here is my answer to this problem :

Sorry about that bad drawing. My problem here is at time 13. At this time we have two processes of equal priority ( p1 and p3 ) that we need to schedule them using RR with a quantum of 3 . My question is what process we will start scheduling it here ? I have started with p1 as it was already being executed by the CPU . Also is the rest of the answer is right ?

2) Now for the second question. Let's consider that We need to schedule the same process with a round-robin with a quantum of 4 . I have used this website to check my answer http://cpuburst.com/ and here its answer :

According to this answer, at time 20 p4 should be executed, but according to my answer p1 is the process that should be executed ?? And due to this difference, the rest of the answer is different to mine.


texts: How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps

texts:
Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells in that square. We want to synchronize all cells in the square, so we basically want to solve the firing squad synchronization problem.

Synchronizing all cells in $\Theta(\sqrt{n})$ is rather easy: All cells at the left and right border of the square serve as generals and we synchronize each row separately with any standard 1-dimensional FSSP algorithm. A row of $k$ cells with generals at both ends can be synchronized in $\Theta(k)$ steps (in our case: $k=\sqrt{n}$).

What I want to do, is to synchronize the whole square in $\Theta(\sqrt{n} \log n)$, so I need to slow down the synchronization process by a factor of $\log n$. But I have no idea how to do so.


texts:
I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists in the table and we can return the record associated with Ki.

Since the leaf nodes have the same structure of internal nodes, how can the algorithm know if a node is a leaf node ?


texts: Can Turing Machines decide on computability?

texts: Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?


texts: Is bounded waiting satisfied in the 2 Process Solution?

texts:
Suppose, There are $2$ processes $P1$ and $P2$.

It is given that Mutual Exclusion and Progress are satisfied by these $2$ processes.

Suppose, Programming protocol is designed such that CPU only executes $P1$ and $P2$ is never alloted the CPU, So, here $P2$ starves.

My Question :- Is Bounded Waiting satisfied here ?

I think BW is satisfied, as there exists a bound on the number of processes that
may enter after process desires to enter CS. And, here that bound is only 1 as only $P1$ is getting executed and if suppose CPU stops executing $P1$ and then after that only $P2$ will be executed.

Please provide the reason that exactly what happens here ?


texts: Is there any algorithm so it can solve stable marriage problem with incomplete preference lists

texts:
I have a slightly different formulation of the stable marriage problem. Basically, I can match one man to one woman, but the preference list is incomplete, which means that a man has expressed interest only in a subset of women and vice versa. I don't think the original Gale Shapley algorithm would work for this, if so what modifications do I need to make? If Gale Shapely does not work here, is there any algorithm to solve this? code suggestions, especially in python for this kind of problem, are very welcomed.

Men = [1, 2, 3, 4, 5]
Women = [a, b, c, d, e]

preferences:

men:
1: a, c, d
2: d, a, b
3: a, e, b
4: c, a, d
5: e, d, a

women:
a: 1, 3, 4
b: 4, 2, 5
c: 5, 1, 4
d: 3, 2, 1
e: 5, 3, 1

I need to match each man to one and only one woman

and the number of preferences allowed is fixed and less than the number of candidates.


texts: return all strings contains given string in suffix tree

texts:
Here is my question:

Given a compressed suffix tree of string S and a substring T.
I need to return all substrings of S that begins with the substring T
sorted by lexicographic order.

My approach:
I can traverse the suffix tree and find the edge / node which last letter of T is written on it.
The subtree of this edge basically should be all the substrings of S beginning with the string T.

Am I right about this one?
And How can I print all this subtree sorted?


texts: What is the activation function, label and loss function for Hierachical Softmax

texts:
Several papers(1 (originator), 2, 3) suggest the use of Hierachical Softmax instead of softmax for classification where the number of classes is large (eg many thousand).
I haven't been able to get clear in my head what this means the actual final layer and output/labels of the neural network are.
For (plain) softmax the activation function is the softmax function: $$\mathbf{\hat{y}}=\sigma(\mathbf{z})_j = \frac{e^{z_j}}{\sum_{k=1}^K e^{z_k}}$$
and the loss (error) function is cross entrypy $$C(\mathbf{\hat{y}},\mathbf{y})=\sum_{k=1}^K-\mathbf{y_k}\times \log{\mathbf{\hat{y}_k}}$$ where y is "one-hot" -- all zeros except a 1 for the index matching the class (this lead to effient implementation, if you know the class indexes).
For Hierachical Softmax:
What is the form of the label y, the activation function $\sigma(\mathbf{z})$ and the loss (error) function $C(\mathbf{\hat{y}},\mathbf{y})$
I am starting the suspect that the label is a Binary code for the class, eg a Huffman code, and the activation function is simply sigmoid (or tanh) and the loss is just squared error.
Is that all there is too it?
Or is it infact done with a multilayer network, in some way? (Obviously you
can't stack softmax layers as inputs to softmax layers).
Implementations
There are quiet a few implementations around, but I find all of them hard to follow.

Word2Vec in C, and Gensim in Python.

I'm not great at understanding C -- too many clever tricks (like using 1D indexing + offsets on 2D arrays), and the python harks close to the C (it is an enhanced translation).
There are two linked articles A, B which go someway towards explaining the C code.

A very different python (Cython actually)

A even more different Python (Theano) implementation. This one is not truly Hierarchical soft-max as it only has two layers.

Papers

Morin, F., & Bengio, Y. (2005, January). Hierarchical probabilistic neural network language model. In Proceedings of the international workshop on artificial intelligence and statistics (pp. 246-252).
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., & Dean, J. (2013). Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems (pp. 3111-3119).
Wang, Y., Li, Z., Liu, J., He, Z., Huang, Y., & Li, D. (2014). Word Vector Modeling for Sentiment Analysis of Product Reviews. In Natural Language Processing and Chinese Computing (pp. 168-180). Springer Berlin Heidelberg.


texts: Is this distribution of amount to set by weight a type of Bin Packing Problem and what are names of common algorithms to solve?

texts:
Does the following requirement, or subsets of it, have a problem name I can use to explore optimal solutions?
I struggled to find a good Question Title.
I need to distribute an amount(Freight) to Invoice Lines weighted by Cost when possible. The result should have at most 2 decimal places. Some examples of this problem will have a remaining amount.
Problem => Given Freight = $12.01, calculate weighted freight for each item.
An example with 2 potential acceptable outcomes. Result(2) is optimal as its contains the smallest difference in ratio between itself and Cost.
        Qty  Cost Result(1)        Result(2)
ItemA | 3  | $2  | $1.97 => $5.91 | $2.01 => $6.03
ItemB | 2  | $3  | $3.06 => $6.12 | $2.99 => $5.97
Have no remainder.

This seems to be a Bin Packing Problem similar to this SO.
Any direction is appreciated.
Update
I have modeled the problem with Pseudo code as such but its exponentially expensive as the number of items in the list grow.
Current Proposed Solution is:
BasFreight = @BF
ItemCost = @IC
ItemQty = @IQ
ItemsWeight = @IW
SumOfItemWeights = @SW
SumOfApproxFreights = @SAF

Calculatate each Items aproximate Freight as ToDecimal( (@IW / @SW) * @BF ) / @IQ )

@Delta = @BF - @SAF;
If @Delta !== 0 {
    // Can penny be added?
    Does any qty == 1, if so add @Delta to largest @IW
    Else
    Place @IQ into any combination of 2 sets such that Set1 - Set2 == 1;
    // From this point the problem becomes..
    // Given a list of numbers, find any 2 sets where the difference is 1.
}

Now the problem becomes.  For any set of numbers.  Does a pair of sets exists where numbers in the first are in at most 1 set and the difference of the sets is 1?


texts: Can a regular language have uncountably many strings?

texts: Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward no, but I can't really back it up.


texts: Data structure for set of intervals - query for all intervals contains given point

texts:
We're given a set of $n$ intervals $[a_i, b_i]$, $i=1...n$.
I am looking for a data structure which makes it possible to query for all intervals that contain the point $x$.

My proposition is using two-dimensional interval (sometimes name is segment) tree.   Each query will take $O(\log^2 n + k)$ time, where $k$ is number of interval such that contains point $x$.

Is this correct?  Is there a better solution?


texts:
I'm not sure this is equivalent to bipartite vertex cover question. The question is:

Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex from the left side.

e.g. In the following graph, the answer is 1, cause vertex g has connection to all vertex on the left.


texts: Three Partition-Function Algorithms Comparison

texts:
I have implemented three algorithms codes, in Swift:

1- Polynomial coefficient:

 // create polynomial
func arrangePoly(ofTerms term: Int, toLength len: Int) -> [Int] {
    var a = Array(repeating: 0, count: len+1)

    for i in stride(from: 0, to: a.count, by: term) {
        a[i] = 1
    }
    return a
}
// polynomial product
func productToN(array1 a: [Int], arrayb b: [Int], toPower n: Int) -> [Int] {
    var res = Array(repeating: 0, count: n+1)

    for (pa, ca) in a.enumerated() {
        for (pb, cb) in b.enumerated() {
            if pa+pb <= n {
                res[pa+pb] += ca*cb
            }
        }
    }
    return res
}
// test code: partition of N
var p1 = arrangePoly(ofTerms: 1, toLength: N)
var res = p1

for i in 2...N {
    res = productToN(array1: res, arrayb: arrangePoly(ofTerms: i, toLength: N), toPower: N)
}
print(res[N])   // coefficient of x^N

2- Euler recurrence relations:

func eulerPartition(_ n: Int) -> Int {
    if n < 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k <= n {
            let sign = power(-1, k-1)
            sum += sign * (eulerPartition(n-(k*((3*k)-1)/2)) + eulerPartition(n-(k*((3*k)+1)/2)))
            k += 1
        }
        return sum
    }
}

3- Divisor sum formula:

// sigma(k) is the well-known sum of divisors of k
func part(_ n: Int) -> Int {
    if n < 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k <= n {
            sum += sigma(k) * part(n-k)
            k += 1
        }
        return sum / n
    }
}

All the three versions gives the same results for each n >= 1, but with different efficiency. While the Euler recurrence algorithm is assumed, theoretically, to be the fastest of the three, the polynomial coefficient algorithm works the best on my core2duo  laptop in spite of it is not recursively coded like the others. I am sure I have done something wrong, but I can not figure what or where.

Any idea?


texts:
Is there a numbering (not Gödel numbering) of all computable functions $U(p, x)$, such that the set of numbers of functions defined in zero is exactly the set of even numbers. More formally: $I = \{p,\ |\ U(p, 0)\  \mathrm{defined}\} = 2\mathbb{N}$.

My guess that it's true. But I'm not sure how to prove it.

Ideas:

We can construct a numbering of all computable functions, defined in zero using the function $F(p, x, t)$ which is equal to $0$ if $U(p, x)$ hasn't finished work in $t$ steps and $1$ in other case. We can do it because set of pairs $(p, t)$ is enumerable.

Then, having this function $V(p, x)$ and some other numbering $U(p, x)$ we can construct numbering

$$
U'(p, x) =
\begin{cases}
V(\frac{p}{2}, x)\ \ if\ p \vdots 2\\
U(\frac{p + 1}{2}, x)\ \ if\ p \not\vdots 2
\end{cases}
$$


texts: Why don't computers use the same architecture?

texts:
We just started on the Computer Architecture topic in our CS lectures and I have a few questions that are currently bothering me. So we have different computers, and there are always differences in the hardware and architecture.

Now, why don't all computers simply use the same architecture? Won't that make it easier to program? What makes this a bad idea?


texts: DFA that accepts decimal representations of a natural number divisible by 43

texts:
First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. For this I choose the states $Q = \mathbb{Z}/3\mathbb{Z}\cup\{q_0\}$ ($q_0$ to avoid the empty word), start state $q_0$, accept states $\{[0]_3\}$ and $\delta(q, w) =\begin{cases} [w]_3 &\mbox{if } q = q_0 \\
[q + w]_3 & \mbox{else } \end{cases}$

Of course, it doesn't work that way for natural numbers divisible by 43. For 43 itself, I would end in $[7]_{43}$, which wouldn't be an accepting state. Is there any way I can add something there or do you have other suggestions on how to do this? Thanks.


texts: Lower bound on algorithm solving certain recurrence

texts:
I have to find the lower bound of the following recursion:
$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Evaluate $F_n$.
\begin{align}
A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}, \\
B_{k+1} &= (B_k + 2D_k) (1-p_{k+1}) + p_k (1-p_{k+1}), \\
C_{k+1} &= C_k p_{k+1} + (1-p_k) p_{k+1}, \\
D_{k+1} &= D_k (1-p_{k+1}) + p_k (1-p_{k+1}).
\end{align}
In this case all numbers of the form $p_i$ are given inputs (there are $n$ of them).
I have to find the lower bound of this algorithm.
Since it's runtime is just $O(n)$ (right?), I know for sure that the maximum possible value of the lower bound is $\Omega(n)$. How would I go about proving/disproving that $\Omega(n)$ truly is the minimum bound  and that $\Omega(n-1)$ is not/is attainable?
The only main method I know for proving stuff like this is an Adversary Argument but after a couple hours of thinking, I still haven't been able to come up with an argument to prove what I want.
Any helps/tips/suggestions would be greatly appreciated.


texts: Finding a particular path in weighted tree

texts:
I have undirected weighted linear tree (path tree) with $n$ nodes ,and
a weight function on edges $\omega: \mathbb{N}\to  \mathbb{N}$,
additionally given $k\in \mathbb{N}$, How we can find a path with
lenght $k$ that have minimum number of edges in $O(n)$?<img src="https://i.stack.imgur.com/HGEwH.png" alt="enter image
description here" />

I think as follow:
Run Bellman Ford for each node and then select a path with length $k$ and minimum number of edges. Unfortunately runtime $\omega(n)$.


texts: Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program?

texts:
Chapter 7 of The Haskell Road to Logic Math and Programming discusses induction and recursion.

Haskell is strongly typed and we can define the natural numbers

data Natural = Z | S Natural
deriving (Eq, Show)

and we can try to construct addition

plus m Z = m
plus m (S n) = S (plus m n)

Can we write a program that proves that addition is associative $(a+b)+c = a+(b+c)$?
Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$?

Is it possible to write a program (e.g. in Haskell) that proves the equivalence of two other programs?

https://stackoverflow.com/questions/4077970/can-haskell-functions-be-proved-model-checked-verified-with-correctness-properti

  Model-checking a general purpose language is neigh impossible since models must be domain specific to be practical. Due to Gödel's Incompleteness Theorem, there simply is no method for automatically finding proofs in a sufficiently expressive logic.

  This means that you have to write proofs yourself, which raises the question of whether the effort is worth the time spent. Of course, the effort creates something very valuable, namely the assurance that your program is correct. The question is not whether this is a must-have, but whether the time spent is too great a cost. The thing about proofs is that while you may have an "intuitive" understanding that your program is correct, it is often very difficult to formalize this understanding as a proof.

This blog says associativity and other simple statements can be proven in Haskell using the Curry-Howard correspondence.  Not entirely sure what that is.

https://jeltsch.wordpress.com/2012/04/30/dependently-typed-programming-and-theorem-proving-in-haskell/

assoc :: Nat nat1                                          ->
         Nat nat2                                          ->
         Nat nat3                                          ->
         (nat1 :+ nat2) :+ nat3 :== nat1 :+ (nat2 :+ nat3)
assoc Zero        nat2 nat3 = Refl
assoc (Succ nat1) nat2 nat3 = case assoc nat1 nat2 nat3 of
                                  Refl -> Refl

The program compiles and therefore the proof works.

Apologia

I am an experience mathematicians, but I am new to how programmers and CS people think about proofs and theorem-proving.  So please excuse me if I confuse one branch of math for the other.


texts: What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?

texts:
Consider the highlighted columns in the following table:

Starting with 100,000 newborns, $l_{x+2}$ denotes the number of individuals in the sample still alive at age $x+2$. If we consider Makeham's law of mortality, defined by the function
$$
S_0(x) = \exp \left( -Ax - \frac{Bc^x - 1}{\log (c)} \right)
$$
we find that for the correct parameters $A, B$ and $c$ this formula very closely models the actual number of deaths.

So my question is this, given a data set and a model with unknown parameters, what computational method may be used to approximate the optimal parameters for the model (which most closely fit the given data set)?

As a more simple example, suppose we are given the data set
$$
X = \left\{ 1, 3, 5.1, 7, 9 \right\}
$$
and are required to find the optimal parameters $A$ and $B$ such that the model
$$
f(x) = Ax + B
$$
most closely fits this data set. As humans, it is clear to see that the optimal parameters are $A = 2$ and $B = 1$. How might a computer deduce these values?


texts: Is this possible that quantum computer will be able to violate the Church thesis?

texts:
After reading Church's thesis, and godelization theory, it seems everything is futile, is this really true, all the machines we are making machine which is same as before, bounded to not solve halting problems, in more simple terms can quantum computer do anything that a Turing machine can't?
PS: In book named Elements of theory of computation first edition, you will find Godelization otherwise it is redacted since second edition reason unknown but chapter 5 named Church Thesis is highly altered since second edition.


texts: How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?

texts:
In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. The algorithm discussed is a Monte Carlo algorithm. As such if we would like to run this variation of algorithm till we find a solution, how do we show that it still has a linear running time?

The Algorithm (source, starts on slide 66, page 53):

  Input: A set $S$ of $n$ elements over a totally ordered
  universe$^{***}$.

  Output: The median of set $S$, denoted by $m$.

  Pick a (multi-)set $R$ of $\lceil n^\frac{3}{4} \rceil$ elements in $S$ chosen independently and uniformly at random with
  replacement.
  Sort the set $R$.
  Let $d$ be the $(\lfloor \frac{1}{2} n^\frac{3}{4} - \sqrt{n} \rfloor)$-th  smallest element in sorted set $R$.
  Let $d$ be the $(\lceil \frac{1}{2} n^\frac{3}{4} + \sqrt{n} \rceil)$-th  smallest element in sorted set $R$.
  By comparing every element in $S$ to $d$ and $u$, compute the set: $$C = \left\{ x \in S : d \leq x \leq u \right\}$$ and the numbers
  $$\ell_d = |\{x \in S : x  < d\}|$$ and the numbers $$\ell_u = |\{x
 \in S : x > u\}|$$
  If $\ell_d > \frac{n}{2}$ or $\ell_u > \frac{n}{2}$ then $FAIL$.
  If $|C| \leq 4n^\frac{3}{4}$ then sort the set $C$, otherwise $FAIL$.
  Output the $(\lfloor \frac{n}{2} \rfloor - \ell_d + 1)$th element in the sorted order of $C$.


texts: Solving an ordered knapsack problem exactly with a non linear (blackbox) evaluation function

texts:
Thanks in advance for the help.

I have the following problem which, for lack of a better description, I'm referring to as the problem I've listed in the title.

Specifically I have a knapsack problem where I must exactly fill the knapsack.  Additionally, the order in which I place the elements into the knapsack affects the strength of the solution (but not the volume of the individual elements).  The function that is used to evaluate the strength, or goodness, of the packing is non linear and very complex.  Because of this, I have a model that I will use to repeatedly simulate my evaluation function to get an idea of the strength of each solution rather than directly evaluating my evaluation function (sort of like a surrogate function).

For example, suppose I have a knapsack of size ten.  The following would be possible solutions assuming integers are the elements that I can place into the knapsack (for all intents in purposes my actual problem can be visualized in this manner): [5,5], [3,3,4], [4,3,3], etc.

What I'm interested in is two-fold.  First, does this problem reduce to any well studied problems from which I could read up more on how they are solved?  I'm currently thinking about using some kind of heuristic search to solve this problem, such as a Genetic Algorithm (I don't have to have the optimal solution, though I would like the best that I can get).  Second and somewhat related to the first, what work if any has been done on problems that fit the description that I have given above?  The knapsack problem is a very well studied problem and I would find it hard to believe if there hasn't been any work done on problems that fit my current one.  Unfortunately though, while I've found work somewhat related to my problem, I haven't been able to find anything that directly reduces to my problem.


texts: Combinations of numbers in an array that sum to a given value

texts:
Given a particular value x and an array A, I'd like some way to determine (without literally checking each possible combination) all of the combinations of numbers in A that sum to it.

Thanks to Jeff Erickson's wonderful algorithm notes, I can write an algorithm that efficiently determines if a sum exists, but I'm having trouble modifying it to actually remember the numbers it uses. The memoized version in the aforementioned notes doesn't seem to admit any way to keep track of anything, particularly because the number of distinct combinations of numbers may well be greater than $x*len(A)$.

If it helps, for my particular purpose, I'm assuming the numbers in my array are monotonically increasing (notably, no repeats.)

Also if the algorithm could be some polynomial combination of the input size and the value we're summing to, and not exponential, that'd be amazing. I plan to run this subroutine many many times, hahaha.


texts: Does cooperative scheduling suspend processes when they perform an  I/O operation?

texts:
Many operating systems references say that with cooperative (as opposed to preemptive) multitasking, a process keeps the CPU until it explicitly voluntarily suspends itself.  If a running process performs an I/O request that cannot be immediately satisfied (e.g., requests a key stroke that is not yet available), does the scheduler suspend it, or does it really keep the CPU until the request can be serviced?

[Edited to replace "blocks on i/o" with "performs an I/O request that cannot be immediately satisfied."]


texts: Algorithm to match / link complementary pairs

texts:
I'm working on a problem where I have a large number of pairs

e.g

1 -> 2

4 -> 3

2 -> 8

..

And a "match" would be considered 1 -> 2 and 2 -> 8 to make 1 -> 2 -> 8, as "1 -> 2" ends with 2 and "2 -> 8" starts with 2.

Given a large set of pairs, i'd like to create the longest possible chain. I know I could brute force it, but I'm wondering if there is a better way

Edit - I can give more precise context for the problem (Sorry, i'm a student currently in data structures who has not taken an algorithms course)

The datapoints in the pairs would be song names  which well flow together. There is a subreddit called "/r/ocrableach" which posts pairs of songs where the ending of one song blends well with the beginning of another song.

An item can appear multiple times in the data set, but i will be discarding repeats as i build my chain.

I'd like to pull posts from /r/ocrableach and try to build the longest continuous playlist based on the song pairs.

If I have the pairs

"Okra -> Bleach"
"Bleach -> I THINK"
"On God" -> "Okra"

I'd like to start constructing a linked list like this:

"Okra -> Bleach" and "Bleach -> "I THINK" match
= "Okra -> Bleach -> I THINK"

"Okra -> Bleach -> I THINK" and "On God -> Okra" match
= "On God -> Okra -> Bleach -> I THINK"

I'm essentially checking if the tail of one pair matches with the head of the "chain" to see if it can be added.


texts: Byzantine Generals Problem - Oral and Signed Messages

texts:
Having just read through Lamport's paper, I was hoping someone could clarify a few things on the Oral and Signed message algorithms.

Why do we have to run $OM()$, recursively by $m$? If a majority of the Lieutenants are loyal, do they not get the correct value by the first round of exchange?
I'm not exactly clear on step 2 of the $SM()$ algorithm:

  If Lieutenant $i$ receives a message of the form $v : 0 :j_1 : \ldots : Jk$
  and $v$ is not in the set $V_i$, then

  he adds v to $V_i$;
  if $k < m$, then he sends the message $v:0 :j_1 :\ldots:j_k : i$ to every
     lieutenant other than $j_1 \ldots j_k$.

Does Lieutenant $i$ only sign a message if $v$ is not already in $V_i$? Does that mean, there is only one message per value getting $m$ signatures on the system? Is that what Lamport means, when they prove that a Lieutenant knows when there are no more messages because there can only be one form of each?

Any tips and help is much appreciated!


texts:
I have written a program which contains a while loop: while k < sqrt(n), so clearly my program evaluates $\sqrt{n}$ at each iteration of the while loop. (Note that $n$ and $k$ can both change throughout the loop, although I do not think that this is relevant to the question.)

I am required to calculate the number of arithmetic operations used by my program in terms of the initial value of $n$ (in terms of the number $n$, not the number of digits of $n$) when it is run, where an arithmetic operation is defined as the addition, subtraction, multiplication or division of any two numbers.

My question is, how many arithmetic operations does $\sqrt{n}$ use? Is it a fixed amount or does it change with $n$ (and if so to what extent)?


texts: What is the name two mutually idempotent functions?

texts:
To clarify, in haskell, there is an ord function that gives the byte integer of a character (i.e. ord 'a' yields 97); and there is a char function that takes the byte integer of a character and returns the character (i.e. char 97 yelds 'a'.

What is the name of a collection of such functions? I'm not very mathematically literate (I'm working on it), but I found semirings on wikipedia. Do semirings provide an appropriate description?


texts: Proof of a greedy algorithm used for a variation of bin-packing problem

texts:
We are given an array of weights $W$ (all weights are positive integers), and we need to put the
weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The variation is that the ordering of weights should not be changed, that is, $W_i$ should be inside a bin before $W_j$ is inserted, for all $i < j$.

For this problem statement, intuitively we can see that a greedy approach of filling a bin till its maximum value is reached and creating a new bin for further weights will produce the minimum number of bins. I am unable to come up with a formal proof that the greedy solution is optimal. Any hints or guidelines would be great!


texts: Modifies Dijkstra’s Algorithm to find the maximum cost path

texts: In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?


texts: Condition in Shamir Secret Sharing Scheme

texts:
For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$).  The constant coefficient of this polynomial is defined to be the key.  Then the scheme sends to player $i$ the value $q(i)$ (for $i \leq k$ for some fixed $k$). The interpolation theorem says that if $n$ players come together, then I can use interpolation to reconstruct the polynomial (there is a unique polynomial $p$ of degree at most $n-1$ such that $p(i)=q(i)$ .. in otherwords $p=q$.  So that I can grab the constant coefficient of $p$ and it must be the same as the constant coefficient of $q$, and hence must be the key).

The question I have, is that what if the polynomial is degree less than $n-1$.  There seems to be nothing in the construction as described by Shamir that prevents this.  However, Shamir states that $n-1$ players cannot reconstruct the polynomial.

The problem I am having is that there seems to be a "most of the time" clause missing. If I happen to pick a degree one polynomial then any two players can reconstruct the polynomial.  So is it that the players do not know the degree of the polynomial, or that the probability of picking a small degree polynomial is low enough that the probability of two participants guessing the key is still the same as random guessing, or am I missing something else.


texts: Are two strings equal if all deciders for a language take the same amount of time for both?

texts:
Let $X_*^L$ be the set of all deterministic Turing machines $M$ which decide the language $L$ and have the property:

$\forall x,y \in \Sigma^*: t_M(xy) \ge t_M(x) + t_M(y)$ (**)

where $t_M(w)$ is the time of $M$ on input $w$.

Define for all $x,y\in \Sigma^*$:

$d(x,y) := \max_{M \in X_*^L} \frac{|t_M(x) - t_M(y)|}{t_M(xy)+t_M(yx)}$

Then, because of (**) we have
$t_M(yx) + t_M(xy) \ge 2(t_M(x)+t_M(y))$ from which it follows that:
$\frac{|t_M(x) - t_M(y)|}{t_M(xy) + t_M(yx)} \le 1/2 \frac{|t_M(x)-t_M(y)|}{t_M(x) + t_M(y)} \le 1/2 \frac{ |t_M(x)| + |t_M(y)|}{t_M(x) + t_M(y)} = \frac{1}{2}$
Hence we get
$d(x,y) \le 1/2$.

My question is this:

Does $d(x,y) = 0$ which is equivalent to $\forall M \in X_*^L: t_M(x) = t_M(y)$ imply that $x = y$?

The reason for asking this question, is that I am trying to define a metric on strings which has "something to do with the time-complexity of Turing machines".
If we define $d(x,y) = \max_{M \in X^L} |t_M(x) - t_M(y)|$ (where the maximum is taken over all machines which decide $L$.). Then I can show, that $d(x,y) = 0$ implies $x = y$. But the problem with this definition, is that $d(x,y)$ can be $\infty$. Or am I wrong with this?


texts: In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be "shortest"?

texts: Occam's razor states that shorter explanations (formally speaking, hypotheses) are more likely to be correct. Indeed this can be formalized: for a hypothesis class $\mathcal H$ one may ascribe representations to each hypothesis and take their literal length as strings. The shorter ones are more correct. But the problem is I can just rearrange the language to make perverse hypotheses shorter, at which point they will be more likely. This seems contradictory. What gives?


texts: Proving NP hardness about graph creation problem with triangle number

texts:
I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in the graph. Given the above constraints ($n+1$), I have to generate a graph that satisfies all the constraints.

I know that given nodes' degrees, it is possible to construct using Havel–Hakimi algorithm a graph satisfying node degrees. But I am not sure how to fulfill the total triangle count constraint and if it makes the problem NP-hard.


texts:
My lecturer recently released solutions to an assignment. One of the questions was to determine the weakest precondition of:

{y < 10} if (x > 0 OR y < 10) -> y:=10 fi {true}

According to the provided solution, the weakest precondition of the selection command

(x > 0 OR y < 10) -> y:=10

is

(x > 0 OR y < 10)

I understand how the weakest predicate was arrived at, but why does the solution then state that the total assertion is true because

 (y < 10) IMPLIES EVERYWHERE (x > 0 OR y < 10)

Isn't y < 10 weaker than (x > 0 OR y < 10)? Therefore, there are potential precondition states where y < 10 but x !> 0. Since the program doesn't have guards for such a condition, it then aborts.


texts: Split-Find: maintaining dynamic graph connectivity information, under edge deletion

texts:
Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph?

Let $G$ be an undirected graph.  I have two operations I'd like to be able to perform:

Delete$(u,v)$: delete the edge $(u,v)$ from the graph.
SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected component

Is there a data structure that allows me to perform both operations relatively efficiently?

The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable.  However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm.  Is there a data structure where both operations can be done in sub-linear running time?

One way to think about it is that I am basically asking for the dual of the Union-Find data structure.  The Union-Find data structure offers two operations:

Union$(u,v)$: add an edge $(u,v)$ to the graph.
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

You could think of this question as asking for a Split-Find data structure, which should support two operations:

Split$(u,v)$: delete the edge $(u,v)$ from the graph.
Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

As we know, there is an efficient Union-Find data structure.  The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too.

Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be implemented by calling Split$(u,v)$, and SameComponent$(u,v)$ would be implemented by testing whether Find$(u) = $ Find$(v)$.

So, is there an efficient Split-Find data structure?


texts: LTL properties in bounded model checking via assertions

texts:
Is there a way to check LTL properties in a bounded model checker?

As an example, consider a liveness property ($G F p$ - always eventually $p$)? Suppose we have the following trivial program

#include <pthread.h>
int a = 0;
void * f(void * x)
{
  a = 1;
  return x;
}
int main()
{
  pthread_t t;
  pthread_create(&t, 0, f, 0);
  while (a == 0);
  return 1;
}

Is "always eventually main terminates" expressible in a bounded model checker using only assertions?

In principle, you can construct a Büchi automaton from an LTL formula, express it in the modeling language (e.g. as C code) and run it in parallel to the model/program. However, unbounded loops pose a problem to the bounded model checker. Hence, I wonder how such properties can be expressed using assertions, e.g. in CBMC.


texts: Understanding CRC Computation with PCLMULQDQ

texts:
I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet.

Starting with this one for the definition of crc32:

CRC (M (x)) = xdeg(P(x)) • M(x) mod P(x)
Before reading this paper, I had only ever seen CRC (M (x)) = M(x) mod P (x). Why can xdeg(P(x)) be multiplied with M(x) (and still =CRC) and why do they do it?

M(x) = D(x) • x^T xor G(x).

Again I do not understand how they derived this equation?

I also don't understand why they are using multiplication at all (although this might become clear once I understand 1) and 2).

All CRC implementations I've seen so far are basically divisions with or without precomputed values so why do they use multiplication?

In addition, I'd also be very thankful to be pointed towards resources that could help me derive these equations myself in the future.
EDIT: Ive managed to derive 2). Any bitstring M representing a polynomial can be cut into two smaller bitstrings A and B. To add them back together to create M you have to multiply A by x to the power of the number of digits(=T) in B, thereby appending T zeros to the right end of A. Once you've done this, you can xor (add in galois field) the two back together, creating M. E.g. M = 10101, A = 101 B = 01 => T = 2; A * x^T = 10100. Xor with B = 10100 xor 01 = 10101 = M
EDIT2: typos


texts: An FPT algorithm for Hamiltonian cycle running parameterized by treewidth

texts:
I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$ time.

In other words, once you have the treewidth, an algorithm that says if the input graph has a Hamiltonian cycle.


texts: Progressive discrete multifunction optimization

texts:
I have a set of functions $F$.

The functions effectively take a set $S$ that is always a subset of a global set of all possible values $G$, where $|G|>1000$. (alternatively, they could take a $|G|$tuple of booleans, if that's easier). The functions return a real result. I want to minimize over $S$ the average value of these functions if all of them are given the same parameter $S$.

$$\min_{S\,\subset\, G}\left(\sum_{f\,\in\,F}f(S)\right)$$

Now here's the catch:

The functions take a fantastic amount of time to run (say, a few hours), and I intend to have a huge collection of such functions (say $|F|>1000$ to start). Every so often, a new function will be created and be added to the set. There is no bound to the size of $F$.

Obviously, I can't just use closed form optimization (I'll be dead before it'll finish), so I'm interested in an algorithm that can find an approximate solution and progressively refine it over time as new function results and new functions come in (and hopefully converge faster than brute force).

We can have a better-than-brute-force because the functions $F$ behave similarly. Namely, $f(S) \approx f(T)$ when $S\approx T$ and $k_aF_a(S) \approx k_bF_b(S)$ for all $S$ ($k$ is constant). There are, of course, many exceptions.

Now, I am new in the CS field so I have no idea what things are called. AFAIK I haven't learned how to do this in Into to ML, but it has the feel of a Genetic Algorithm problem. If anyone could point me to a technique or a name, I'd be very happy.


texts:
Suppose I have a admissible and consistent heuristic.

Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?

Look at this pseudocode from wikipedia:

function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor]
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

I suppose it should be true. Because of this:

if current = goal
     return reconstruct_path(came_from, goal)

If it wasn't true then this test would not guarantee me that the solution is optimal right?

What I don't get and the reason I am asking this question is this:

if neighbor in closedset
         if tentative_g_score >= g_score[neighbor]
             continue

If the neighbor is in closed list, it means that it has already been expanded. Why are they testing the scores then? Why would not the next condition work?

if neighbor in closedset
         continue


texts: What's wrong here, or, is CNF to DNF conversion in o(exp(n))?

texts:
I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and $l=2$:

$(a \lor b) \land (c \lor d) \land (e \lor f)$

Obviously, this will result in a DNF of length $k^l$, as all possible conjunction combinations need to be listed and due to all variables being unique, nothing will vanish.
Given that, computation time complexity will at least be exponential and lay in $o(k^l)$.

Now, two questions:

Can we say that time complexity will also be within $o(exp(n))$, where n denotes formula length?
If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is NP-hard NP-complete, that $P \neq NP$?
Edit: I'm aware CNF -> DNF is NP-hard, but is it NP-complete too?


texts: How to prove that $n\log n$ is space constructible?

texts:
I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that if both $n$ and $\log n$ are space constructible, $n\log n$ will be space constructible as well.

I'm using Sipser's definition of space constructibility:

  A function $f\colon N\to N$, where $f(n)$ is at least $O(\log n)$, is called
  space constructible if the function that maps the string $1^n$ to the
  binary representation of $f(n)$ is computable in space $O(f(n))$.


texts: Sieving to compute first values of totient function

texts:
What i want to do is to compute the first $n$ values of Euler's totient function effectively. As far as i know the best way to do it is to run a sieving algorithm and for each prime encountered to update current totient-value for all its multiples. My realization in Python is given below. I use two facts about totient function:

a) if $~p~$ is prime than $~\phi(n) = n-1$

b) for any prime $~p~$ and positive integers $~a,n~$  $~\phi(p^a n) = p^a n (1 - \frac{1}{p})$

My problem is termination of main loop. My code loops till $n / 2$  though i would like to stop at $\sqrt{n}$. The problem is that some numbers above $\sqrt{n}$ may have prime divisors above $\sqrt{n}$ which won't be processed with current version of algorithm if main loop is terminated before $n / 2$. I don't understand how to handle totient function values for such numbers since calculation for them wasn't finished in fact. Any ideas on these problem will be highly appreciated. Thanks in advance!

# n >= 2
def sieve(P, n):
    end = n // 2 + 1
    for k in range(2, end):
        if (P[k] == k):
            for j in range(2*k, end, k):
                P[j] -= P[j] // k

def phi(P, n):
    if (n == 1):
        return 1
    if (P[n] == n):
        return n-1
    return P[n]

n = int(input())
P = [i for i in range(0,n+1)]
sieve(P, n)
for k in range(1, n+1):
    print(repr(k) + "  " + repr(phi(P,k)))


texts: Adder-Subtractor Circuit With Negative Results

texts:
So, I understand how binary arithmetic works, and I understand how an adder-subtractor works for signed numbers. There is only one thing I am not sure about:
All the cases work ok in the circuit I have, except if the result of a subtraction is negative, I need to take the two's complement of the output byte to get the actual result. What can I do about it? Do I need an extra array of adders to compute the two's complement only in that specific way, or is there any smarter solution I can apply?
Thanks in advance.


texts: How does sorting come into play with convex hull?

texts:
I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane.

That algorithm first sorts the points by x-coordinates. It then includes the first and last points in the convex hull. From there on, I am confused. How could an algorithm like this get the other points of the hull?


texts: Complexity of k-way merge with log n arrays of size n / log n

texts:
I'm designing an in-place sorting algorithm to sort a collection of size $n$. Near the end of the sorting, it may end up with with $\log{n}$ sorted sub-sequences of size $\frac{n}{\log{n}}$. At this point, I use a very simple $k$-way merge algorithm that merges the sub-sequences pairwise until everything has been merged. This very case apparently represents the complexity bottleneck of the algorithm.

I'm repeatedly using the C++ function std::inplace_merge to perform the merging operations, which performs $Θ(N \log{N})$ comparisons most of the time, but may perform up to $O(N \log^2{N})$ comparisons if there isn't enough extra memory available, where $N$ corresponds to the sum of the sizes of the sequences to merge (in our case $2\frac{n}{\log{n}}$).

Taking all of that information into account, I can tell that repeatedly merging the sub-sequences pairwise until everything has been merged takes the following number of comparisons, step by step:

Step 1: $O(\frac{\log{n}}{2} * \frac{2n}{\log{n}} * \log^2{\frac{2n}{\log{n}}}) = O(n * \log^2{\frac{2n}{\log{n}}})$
Step 2: $O(\frac{\log{n}}{4} * \frac{4n}{\log{n}} * \log^2{\frac{4n}{\log{n}}}) = O(n * \log^2{\frac{4n}{\log{n}}})$
Step 3: $O(\frac{\log{n}}{8} * \frac{8n}{\log{n}} * \log^2{\frac{8n}{\log{n}}}) = O(n * \log^2{\frac{8n}{\log{n}}})$
$\ldots$

If I'm not mistaken, there will be $\log{k}$ steps where $k$ is number of sorted sub-sequences in the original collection, which is is $\log{n}$, hence there will be $\log{\log{n}}$ steps. This should yield an overall complexity along the lines of $O(\log{\log{n}} * n * \log^2{\frac{?n}{\log{n}}})$.

Now, to be perfectly honest, I've got no idea how to simplify this expression further, and since I'm describing a sorting algorithm, I would like to know whether it is more along the lines of $O(n \log{n})$ or $O(n \log^2{n})$.

Having computed the complexity of the other two steps of the algorithm, it appears that none of them performs more than $O(n \log{\frac{n}{\log{n}}})$ comparisons¹, which is intuitively smaller than $O(n \log{n})$, the lower bound for comparison sorting, so the k-way merge surely dominates the overall complexity and thus performs at least $O(n \log{n})$ comparisons.

Can you help me solve this complexity problem?

¹ Among the other steps, the bigger one is sorting $\log{n}$ sub-sequences of size $\frac{n}{\log{n}}$ with an $O(N \log{N})$ sorting algorithm, which has the complexity $O(\log{n} * \frac{n}{\log{n}} \log{\frac{n}{\log{n}}}) = O(n \log{\frac{n}{\log{n}}})$.


texts: What's the meaning of the $\top$ symbol in a Hoare triple?

texts:
I'm studying program verification and came across the following triple:
$$ \{\top\} \;P \; \{y=(x+1)\} $$
What's the meaning of the $\top$ symbol on the precondition? Does it mean $P$ can take any input?


texts: Problem on Floating Point Representation

texts:
Consider the floating-point representation

31-24 : Exponent
23-0  : Mantissa

The exponent is in 2's complement representation and mantissa is in the sign magnitude representation. the range of the magnitude of the normalized numbers in this represntaion is

  $(a)\ 0\ to \ 1$

  $(b)\ 0.5\ to\ 1$

  $(c)\ 2^{-23}\ to \ 0.5$

  $(d)\ 0.5\ to \ (1-2^{-23})$

My approach:
as the normalized number in floating point representation has as implicit 1.

Hence smallest mantissa would be

  $1.0000\cdots [24\ 0's]=1$

Largest mantissa would be

  $1.1111\cdots [24\ 1's]=1+(1-2^{-24})\approx2$

So my ans coming as 1 to 2, Which is not in the option. What mistake I'm doing..


texts: Meaning of "positive position" and "negative position" in type theory?

texts:
What does "in positive position" and "in negative position" mean in the context of type theory?

The only thing I understood from Bob Harper's blog post on the topic is that there is a connection between polarity in this sense in type theory and polarity in logic, but I don't know what that connection is.


texts: Do static and dynamic scoping matter to the closure of a function?

texts:
If I am correct,

The closure of a function is the non-local environment of the function.
the non-local environment of a function is different depending on static or dynamic scoping.

So is the closure of a function also different depending on static or dynamic scoping?

Thanks.


texts: Trick/insight to I implement given boolean function with minimum numbers of given gate

texts:
I solved bunch of questions which give some function and then ask to implement it with minimum number of gates of specific type, each having specific number inputs. I was making mistakes in all those problems by not implementing given function with minimum number of gates.

Let me give those problems one by one and explain my point.

  Problem 1

  What is minimum number of two input NAND gates required to implement the function:
  $f=\overline A \overline C+\overline A\overline B+\overline B \overline C$

I translated the function directly to the circuit as follows:

Then I converted this to NAND-only implementation as follows:

But when I checked the answer, it was saying lesser NAND gates. So I tried something different. I solved equation as follows:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}$
$=\overline{\overline{\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}}}$
$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

And realized that I will need seven NAND gates for following:

$\overline{A}$
$\overline{B}$
$\overline{C}$
$\overline{(\overline{A}.\overline{C})}$
$\overline{(\overline{A}.\overline{B})}$
$\overline{(\overline{B}.\overline{C})}$
$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

But then I checked detailed solution and found that the solution has come up with following equation:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}\overline{C}$
$=\overline{A}.\overline{C}+\overline{B}(\overline{A}+\overline{C})$
$=\overline{A}.\overline{C}+\overline{B}\overline{(\overline{A}.\overline{C})}$
$=\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

This requires six NANDs:

$\overline{A}$
$\overline{B}$
$\overline{C}$
$\overline{(\overline{A}.\overline{C})}$ (used twice in the equation)
$\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}$
$\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

So I was wrong twice!!!

Problem 2
Another problem gave truth table of the function and asked to implement it with NOR gate. I prepared truth table for it and grouped zeroes as follows:

Knowing that I have to use NOR, I thought I should form product of sum equation of this and then take double negation to get NOR friendly equation. So, I formed equation for it as follows:

$f=(x+\overline y)(\overline x + y)$
$=\overline{\overline{(x+\overline y)(\overline x + y)}}$ (taking double complement)
$=\overline{\overline{(x+\overline y)}+\overline{(\overline x + y)}}$

Now this looks perfect NOR equation as thought and it requires five NORs. But when I checked the solution, I came to know that this is indeed ExNOR equation. The solution formed sum of product equation of K map:

$xy+\overline x \overline y$

and then implemented ExNOR with four NORs, something like this:

Doubt

I have solved many other problems. It almost always turned out that I have followed one approach and the solution followed another to further reduce the GATE count. I feel there should be some steps / methods to get idea how many minimum number of gated are required. I know this problem is NP complete. However I feel that there has to some definite patterns on k map which can lead us / give direction / provide hint to correct final answer.

Can there be any such method? trick?


texts: In counterfactual regret minimization, why are additions to regret weighted by reach probability?

texts:
I'm reading the algorithm on page 12 of An Introduction to Counterfactual Regret Minimization. On lines 25 and 26, we accumulate new values into $r_i$ and $s_i$:

$25.\space \space r_I[a] ← r_I[a] + \pi_{-i} . (v_{\sigma I \rightarrow a}[a] - v_{\sigma}[a])$
$26. \space \space s_I[a] ← s_I[a] + \pi_{i} . \sigma^t(I, a)$

$r_I[a]$ is the accumulated regret for information set $I$ and action $a$. $s_I[a]$ is the accumulated strategy for information set $I$ and action $a$.
$\pi_{i}$ is the probability of reaching this game state for the learning player (for whom we're updating strategy and regret values in the current CFR iteration). $\pi_{-i}$ is the probability of reaching this game state for the other player.
Why do we multiply by $\pi_{-i}$ and $\pi_{i}$ to accumulate the strategy and regret on lines 25 and 26? Couldn't we just do this:

$25.\space \space r_I[a] ← r_I[a] + (v_{\sigma I \rightarrow a}[a] - v_{\sigma}[a])$
$26. \space \space s_I[a] ← s_I[a] + \sigma^t(I, a)$

It seems to me it doesn't matter exactly how much we adjust the strategy and regrets in this CFR iteration—so long as we do enough CFR iterations, won't we end up with good values for $r_I$ and $s_I$ in the end?


texts: Graph Theory applied to a physical logic puzzle

texts:
For Christmas my brother got me this puzzle:

The premise is that you have a metal medallion with a series of holes in it and a metal ring with a slit just large enough to slide it from hole to hole, barring obstacles, like the edge of the map and an obstruction near the top. The goal is to be able to remove the ring from the medallion when starting at the center hole. It was simple enough to figure out after mapping out taken paths, but after solving it, I thought it might be fun to make a solver:

I'm sure something like this has been done and is part of some Legend of Zelda-like dungeon, but I wanted a simple example to demonstrate some concepts in Angular. The Angular part took about 15-30 minutes to throw together after a longer time of working out the nodes and edges.

The Problem

My first thought was that is represented an undirected graph, so I labeled each of the 24 holes with letters A-X and recorded all of the edges as holes that the ring can travel directly between. That works, except for the obstacle (an intentionally raised point) that exists between A, B, C, and D.

In this exact puzzle, the solution is:
Start,M,A,I,F,U,H,K,R,D,Q,V,J,X,P,N,B,Q,End

Applying a simple shortest path algorithm renders:
Start,M,A,I,F,U,H,K,R,D,Q,End

The problem with that solution is that the exit is not reachable from Q until you have gotten on the other side of the raised point at the top, so you have to run through the little cycle of Q,V,J,X,P,N,B,Q to get around it.

I'm getting the vibe that the correct structure may not be an undirected graph or that I need to use something other than the shortest path, but I'm not sure what the terms I need to look for are going to be.

Extra Info

All of the existing edges I've found are:
[["A","M"],["A","I"],["B","N"],["B","Q"],["B","P"],["C","K"],["D","R"],["D","S"],["D","Q"],["E","R"],["E","K"],["F","I"],["F","U"],["G","W"],["H","U"],["H","K"],["H","O"],["H","W"],["I","L"],["J","X"],["J","V"],["K","R"],["M","Start"],["N","P"],["P","X"],["Q","End"],["Q","V"],["T","V"]]

I was going to look into some way to plot the nodes in Angular in a way that correlated to their relative positions on the medallion, but the main problem seemed more important.

Imgur Album


texts: Simple Question About the Nature of Supervised Learning Predictive Models in Relation to their Training Data

texts:
Would a deployed or deployment-ready (i.e., already-trained) supervised learning model have a 100% accuracy rate for predictions on the training data (if you were to run the training data through it again)?

[Note: I don't know if it is possible for such models to incorporate "memory" such that the model would retrieve an output variable for a given training data point (containing various input variables) from memory (having seen it before during training), instead of retrieving it by plugging the data point's input variables into the equation that is the predictive model (obviously a unique, unknown equation created during the training process, with millions of parameters, which no human knows the precise nature of). If it is possible for such models to have "memory", then for the purposes of my question, please assume it is not.]

What I would like to know is: are SL predictive models perfectly parameterized for the training data, such that feeding any training data point in to the completed model will 100% of the time yield the correct output for that data point (note: I am aware that, in general, testing a deployment-ready model on its training data is not a very useful test), or are such models imperfect predictors even if run (when already-trained) on their training data?

I know people talk about overfitting and the bias-variance tradeoff. That would seem to indicate the latter to be the case, but I want to be sure.

Thank you for any answers you can offer!


texts: Scientifically acceptable method for comparing performance of algorithms

texts:
I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the best way to go about measuring performance.

As far as I know, there are two ways to compare performance: writing the code in a compiled language like C and measuring the time of execution, or counting the number of FLOPS. However, I am aware that different processors have different capabilities which results in different execution times on different platforms.

These algorithms will be implemented on low-cost embedded systems (the main application is satellites, where low power is key).

So in summary: what is the scientifically accepted way of comparing the performance of different algorithms?


texts: Disjoint Set - Tree Implementation with Union-By-Rank and Path Compression

texts:
Union-By-Rank and Path Compression is supposed to improve the performance of a tree implementation of a disjoint set.

However, in looking at the UNION(x, y) operation, I noticed that if x and y are actually the roots of the 2 trees being merged, no path compression actually takes place. The resulting tree would simply have a depth equal to the larger depth of the 2 trees.

Is my understanding of the algorithm correct?


texts: Time series probability and mutual information

texts:
There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the program just outputs probability of $1$'s and $0$'s. The following are the questions:

How to find probability or correct my code so that it outputs probablities when number of symbols size > 2?
How to calculate entropy annd mutual information for this case. I don't know although I have read Matlab's entropy calculation Mutual Information & Entropy but alas cannot follow how to apply in this case.


texts:
I have a grocery dotted list of pairs which are missing items that I need and I don't have any of them, so I am going to the supermarket.

Each pair in the dotted list is the name of the missing item that I need and a natural number which is the quantity/amount i.e. how many of this item I need.

I am in the supermarket now and I see an array of packages of items standing on shelf.

There are packages that don't contain items that I don't need and there are packages that contain items that I don't need.

I have enough money to buy all the packages, but if I will do this then I will get items that I don't need, so I don't want to do this.

Surely that I won't buy any package that contains an item that I don't need, but note that I don't want to have too many of any item that I need.

I can peek inside each package to see what items it contains and how many of that item it contains.

I cannot buy partial package, i.e. I cannot for each package decide which items from the package I buy and which I don't buy.

My only choice for each package is either buy the package and get all the items inside or don't buy the package and get nothing from the items that this package  contains.

I want to know if this is possible to buy the packages so I get all what I need exactly as written in my grocery dotted list without having superfluous items that I don't need.

I will bring my mobile phone to the supermarket and once I can peek inside the packages I will run the application that will solve my problem.

I am programmer and I can program this application for my mobile phone with no problem but I want to use a polynomial time algorithm that solves my problem, because I am not going to wait hours, days, months and years until my phone will return me the answer.

But to know if there is polynomial algorithm or not I need to know first if my problem is NP-Hard or NP-Intermediate that polynomial solution is unknown.

Indeed my problem is decision, because I need to decide which packages I buy and which I don't buy and if I have a solution I can verify it in polynomial time, so my problem is indeed in $\mathbb{NP}$, but I don't know if it is in $\mathbb{P}$.

Do you know?

EDIT:

Mathematically my problem is show either:

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\exists C: C \subseteq A \land \displaystyle \biguplus_{D \in C}D=B$

OR

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\nexists C: C\subseteq A \land \displaystyle \biguplus_{D \in C}D=B$


texts:
I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them?

Any help is appreciated.


texts: Is there a difference between pure binary and binary?

texts: In some books and on the internet I occasionally find "pure binary" and "binary" on its own, is there a difference between these two terms? If so, can someone describe briefly what they are?


texts: Correctness of Algorithm for Computing Diameter of a Graph

texts:
I am a TA for an introductory CS course, and one question given to students was how to use BFS to determine the diameter of a graph. The students were told they wouldn't be graded for efficiency, so the expected answer was a brute force algorithm where they ran BFS from every node to every other node and returned the maximum distance from these BFS runs. The students were provided with a BFS method they could reference in their pseudocode which took as an input a node and returned two mappings: one from each node in the graph to its distance from the start node (called distmap), and one from each node to its 'parent node' along the shortest path from the input node (called parentmap).

One student wrote the following algorithm:

1. Choice an arbitrary node from the graph and run BFS from it.
2. Create a set Temp of all the nodes that are not values in parentmap (ie nodes which don't lie upon any shortest paths)
3. Initialize max_dist to 0
4. For each node n in Temp:
    5. Run BFS from n
    6. For each value d in distmap:
        7. IF d > max_dist THEN set max_dist equal to d
8. RETURN max_dist

I believe this answer is correct, but I am unable to prove it. Can someone prove why it works or provide a counterexample?